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.
Sample
| Input | Output |
|---|---|
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.
