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$