As we all know, the number of 's papers follows exponential growth. Therefore, we are curious about sequence.

You are given a prime . A sequence is a sequence if and only if there is an integer such that for all integers , .

Given a sequence , what is the length of the longest  subsequence of ?

A subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements.

is super busy recently, so the only thing he wants to know is whether the answer is greater than or equal to .

If the length of the longest sequence is less than , output . Otherwise, output the length of the longest subsequence.

The first line contains an integer  denoting the number of test cases ().
The first line in a test case contains two integers  and  (, ,  is a prime). The sum of  over all test cases does not exceed .
The second line in a test case contains a sequence  ().

For each test case, output one line containing the answer which is  or the length of the longest  subsequence.

4
6 1000000007
1 1 2 4 8 16
6 1000000007
597337906 816043578 617563954 668607211 89163513 464203601
5 1000000007
2 4 5 6 8
5 1000000007
2 4 5 6 7

5
-1
3
-1