Description

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.

Input Format

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 Format

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

3
5 4
1 2 3 4
5 4
1 2 4 5
6 3
1 3 5

-1
5
-1

Hint

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