Tubby the doggu, likes sets which are closed. Your task is to help him/her solve a problem.

Let's first lay out a few definitions:

Definition 1: A set S is said to closed with respect to a prime number P if and only if:

\( a*b \pmod P \in S \qquad \forall a, b \in S \)

Note that \(a, b\) can be equal.

As an example, the set \(S = \{2, 4, 1\}\) is closed with respect to prime \(P = 7\).

Definition 2: \(Closure(S)\): Closure of a set S is defined to be the smallest closed set containing the set S.

As an example, for \(P = 5\) and set \(S = \{3\}\), \(Closure(S)=\{3, 4, 2, 1\}\)

Definition 3: \(Partition(S)\): Partition of a set S is a set of non-empty subsets of S such that every element of S is in exactly one of these subsets. Moreover, the length of the partition is the number of non-empty subsets required.

As an example, for \(S = \{1,3,7,4,6,2\} \), \(T=\{ \{1, 4, 6\} , \{3, 7, 2\} \}\) is a partition of set S of length 2 as there are two non-empty subsets and each element of S is included in exactly one subset. Also set S itself is a partition of S of length 1.

Now the task is that you are given a prime number P and an array A of N integers , in which the \(i^{th}\) integer is denoted by \(A_i\), \( 1 \le i \le N \), \( 1 \le A_i \lt P \).

You have to partition the set of indices \(\{1, 2, 3, 4, ... , N\}\) into a partition of minimum length such that if \(Closure( \{A_i\}) \subseteq Closure(\{A_j\} )\) then i and j must be in different sets of the partition.

Here, \(i \neq j\) , \( 1 \le i,j \le N \).

Note: x denotes a set containing a single element x.

Input Format

The first line will consist of the integer T denoting the number of test cases.

For each of the T test cases, the first line will consist of two integers P and N, where P is a prime number and N denotes the number of elements.

Next line will consist of N integers, where the \(i^{th}\) integer denotes the element \(A_i\), \( 1 \le i \le N \).

Output Format

For each of the T test cases, output a single integer denoting the minimum length of the partition.

Constraints

\( 1 \le T \le 100 \)

\( 1 \le P \le 10^9 \) ,P is guaranteed to be prime.

\( 1 \le N \le 10^3 \)

Sum of N over all testcases \( \le 25000. \)

\( 1 \le A_i \lt P \) \( \quad \forall 1\le i \le N \)