Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

LIAS 2

Limits: 2s, 512 MB

You will be given an array and an integer K. You have to find the longest increasing sub-sequence from this array so that the following property holds:

Let, the sub-sequence be L. Each consecutive K values in L should give different remainder values if we divide them by K.

You just have to print the size of L.

Input

First line of the input will contain an integer T, the number of test cases. There will be at most 10 test cases.

The first line of each test case will contain two integers N (the size of the array) and K.

The second line of each test case will contain N integers, representing the array.

1 ≤ N ≤ 104, 2 ≤ K ≤ 5

All the values in the array will be in range [0, +108].

Output

Print the desired result. Please have a look at the samples for further details.

Samples

InputOutput
2
10 2
5 16 2 13 5 3 4 3 14 5
9 3
3 17 4 9 6 7 18 8 10
4
4

Dataset is huge. Use faster I/O.

Author
Discussion