Abdou has a set of unique positive integers. He wants to add several (possibly none) new positive integers to this set, such that when the set is sorted, for every two consecutive numbers X, Y abs(X%M-Y%M) = 1 . Your task is to calculate the smallest possible count of new numbers, with which he can achieve that.

Input

The first line contains T, the number of test cases. It is followed by 2*T lines, two lines per test case. The first line contains two positive integers M and N. The second line contains N integers.

1 <= T <= 5000.

1 <= M <= 10^5.

2 <= N <= 50.

1 <= every integer in the set <= 10^6.

Output

For test case print a single integer in a separate line: the smallest possible count of new numbers, with which he can complete the set or -1 if no solution exists.

Example

Input:
5
2 3 
2 10 20
10 2
10 20
10 6
11 19 5 30 40 100
1 2 
1 9999
15 3
4218 15210 1426

Output:
2
1
-1
-1
3

Explanation

In the first test case we can add 3 and 13 to the given set to achieve Abdou's goal.