P8980 "DROI" Round 1 Game

In life, isn’t everything also a game?

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.

**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$.

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`.

#### 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