The test files to this problem were wrong during the contest. To make up for this mistake, the solutions submitted during the contest were rejudged with a time limit of 10 seconds after correcting the test files. Now that the test files have been corrected, the time limit for this problem is 2 seconds itself.

Teacher is explaining about a special class of sequences called the CFC (Climb Fall Climb) Sequence in the class :

" Say there are many mountains arranged one after the other and you are standing at some point of one of them. There are infinitely many mountains on your left and on your right. You start moving towards the right, climbing up and down, up and down. On each side of every mountain, (K-1) villages exist. Apart from these villages, one village exists at the topmost tip of every mountain and one village exists at the intersection point of 2 consecutive mountains. Every time you enter a village, you note down its height from ground. As you visit more and more villages, you write down all these heights one beside the other from left to right. Once you are done visiting some villages, the sequence which you obtain is a CFC Sequence of order K. "

Note: No two villages on the same side of the mountain exist at the same height.

Here is an example for K = 3 (black dots are villages) :

Rani is listening very carefully to Teacher. She starts wondering : "Given a sequence < a_i > of N positive integers, what is the length of the longest sub-sequence of this sequence which is also a CFC sequence of order K ? "

Input

The first line consist of T, the number of test cases. Then, 2T lines follow. The first line of each test case consists of two space separated integers N and K. The next line consists of N space separated integers a_i.

Output

For every test case, print the answer to Rani's question on a new line.

Constraints

1 ≤ T ≤ 10
1 ≤ N ≤10³
1 ≤ K ≤ 10
1 ≤ a_i ≤ 10³

Authors : Shreyans , Ravi