Escape from the Deathland

After waking up, Sunny discovers that he is standing on a strange set of platforms in a circle. There are \( n \) platforms arranged in a circle, numbered \( 0, 1, 2, \ldots, n-1 \) in clockwise order (with platform \( n-1 \) immediately behind platform 0). Initially, Sunny stands on platform 0. Note that the starting position (platform 0) does not count as visited until Sunny lands on it again.

Ethan's voice rings out: "Congratulations, you are the first to set foot in the Deathland." He continues: "You are allowed to jump clockwise. In each move, you may choose any jump length \( i \) with \( 1 \le i \le n \), but I will give you a list of numbers \( a_j \) that are forbidden; you cannot jump exactly \( a_j \) platforms in one move. If you can visit all the platforms (remember, the initial platform 0 only counts when landed on again) using the allowed moves, you will escape from this place. However, you must do so in the minimum number of jumps possible. If you cannot meet both these requirements, all platforms will vanish and you will fall into the lava below."

Your task is to determine whether Sunny can escape the Deathland, and if so, compute the minimum number of jumps needed; otherwise, output -1.

The problem may include multiple test cases.

inputFormat

The first line contains an integer \( T \) (\( 1 \le T \le 100 \)), the number of test cases. Then \( T \) test cases follow.

For each test case, the first line contains two integers \( n \) and \( m \) (\( 1 \le n \le 15 \), \( 0 \le m \le n \)), the number of platforms and the number of forbidden jump lengths respectively. The next line contains \( m \) distinct integers \( a_1, a_2, \ldots, a_m \) (each \( 1 \le a_j \le n \)) representing the forbidden jump lengths. When \( m = 0 \), the second line is omitted.

outputFormat

For each test case, output a single line containing the minimum number of jumps required to visit all platforms (with platform 0 counted only if landed on again), or -1 if it is impossible.

sample

3
4 1
2
3 1
1
5 2
2 4

5
3
5