P5582 "SWTR-1" Escape

One day, when $\mathrm{Sunny}$ was strolling around, he found a button. Curiosity drove him to press the button. Suddenly, the world spun $\dots$

After waking up, $\mathrm{Sunny}$ found himself standing in a strange place. This place has $n$ platforms, **forming a ring**. At this moment, $\mathrm{Ethan}$'s voice sounded: "Ha ha ha ha ha, congratulations. You are the first person to come to the **Land of Death**." "As you can see, this place has $n$ platforms, and you are now standing on platform $0$." "The remaining platforms are numbered clockwise as $1,2,3\dots n-1$. That is, the platform behind you is platform $n-1$." "Each time, you can jump **clockwise** by $i$ platforms, where $i\in[1,n]$, and $i$ may be different each time." "If you can visit all platforms (the initial position $0$ does not count), then you can escape from the **Land of Death**." (Here, the initial position $0$ does not count as visited; you need to visit platform $0$ again.) "However, that is too easy. I will give you some numbers $a_j$, meaning you **cannot jump clockwise by $a_j$ platforms in one move**." "Also, you must complete my task using the **minimum** number of jumps." "If you cannot satisfy the above two requirements, all platforms will disappear, and you will fall into the lava below." Now, $\mathrm{Sunny}$ wants to know whether it is possible for him to escape this place. If not, output ```-1```. Otherwise, output the minimum number of jumps he needs. Because $\mathrm{Sunny}$ thinks the Land of Death is really interesting, he decided to play a few more times, **multiple test cases**.

The first line contains a positive integer $T$, which represents the number of test cases. In the next $2\times T$ lines, there are $T$ test cases in total: Line $2\times i-1$ contains two integers $n,k$, where $k$ is the number of $a_j$ in this test case. Line $2\times i$ contains $k$ numbers, and the $j$-th number is $a_j$.

Output $T$ lines. The $i$-th line is the answer for the $i$-th test case.

--- ### Sample Explanation The first test case: $\mathrm{Sunny}$ can only jump clockwise by $5$ platforms each time, so it is clearly impossible to complete the task. The second test case: $\mathrm{Sunny}$ can only jump clockwise by $3$ platforms each time, and he can do it in $5$ jumps. --- ### Constraints and Notes $0\leq k\leq n\leq 10^6,1\leq n$。 It is guaranteed that $\sum{n_i}\leq 3*10^6,a_j\leq n$, and they are **pairwise distinct**. Test point $1:5\%,n=1$. Test point $2:5\%,n\leq5$. Test point $3:10\%,n\leq15$. Test point $4:15\%,n\leq300$. Test point $5:25\%,n\leq5000$. Test point $6:40\%,n\leq10^6$. --- The dream woke up…… Translated by ChatGPT 5