#214050. [EC Final 2019] King

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.

样例输入 1

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

样例输出 1

5
-1
3
-1