Background

In life, isn’t everything also a game?

Problem Description

You will play $T$ games with a child. The rules of each game are as follows:

1. First, you need to choose a positive integer $x$ in $[1,n]$.

2. Next, the child will make $Q$ queries. For each query, he will give an $a_i$ (guaranteed that $a_i \in [1,n]$), and you need to answer the value of $\gcd(x,a_i)$.

3. After the child gets the answer in some round, if he can uniquely determine the number you chose, then this game ends.

Now you know in advance the $a_i$ for each query. You need to find an $x$ such that the game lasts for as many rounds as possible.

Input Format

This problem has multiple test cases.

The first line contains an integer $T$, indicating the number of games.

For each game:

The first line contains two integers $n$ and $Q$.

The second line contains $Q$ integers, where the $i$-th integer represents $a_i$.

Output Format

For each game, output the maximum number of rounds the game can last. If there exists an $x$ such that the child still cannot uniquely determine its value after $Q$ rounds, output game won't stop.

1
11 3
8 9 5

game won't stop

2
8 5
8 2 3 5 7 
24 16
3 17 18 5 19 4 16 23 7 11 13 18 6 21 22 2

5
11

Hint

Sample Explanation #1

Choose $11$ as $x$. Obviously, the child cannot uniquely determine $x$ until the end of the game.

Sample Explanation #2

For the first test case: choose $1$ as $x$. The child can uniquely determine $x$ after the fifth round ends. It can be proven that no better $x$ exists.

For the second test case: similarly, choosing $1$ as $x$ is enough.

Constraints

"This problem uses bundled testdata."

• $\operatorname{Subtask} 1(20\%)$: $n,Q\leq 500$.

• $\operatorname{Subtask} 2(20\%)$: $n,Q \leq 5 \times 10^4$.

• $\operatorname{Subtask} 3(30\%)$: $Q \leq 10^5$.

• $\operatorname{Subtask} 4(30\%)$: no special restrictions.

For $100\%$ of the data: $T \leq 10$, $1 \leq a_i \leq n \leq 10^{18}$, $1 \leq Q \leq 2\times 10^{6}$, $\sum Q \leq 6\times 10^{6}$.

The input size is large, so please use a faster input method.

Translated by ChatGPT 5