STATEMENT

There are N men standing in a line, and we have K ships available. We can allocate the people to the ships by walking up to each person, in the order they are standing, and telling him which ship to go.

Unfortunately, a person will agree to go on a ship only if there is no one on the ship already who is taller than he is.

Your task is to compute the maximum number of people that can be sent off on the ships, given the heights of all the people. You may assume the heights are distinct, and in fact are 1 to N.

INPUT

The input file will contain several test cases. The first line contains an integer T, the number of test-cases. The succeeding lines contain the test-cases.

Input Format

Each test-case consists of the following:

OUTPUT

The output should contain the solutions to all the test cases, in the order of the test cases in the input. There should NOT be any blank line in the output.

Output Format

For each test case, print a single line containing the maximum number of people that can be sent.

Points and constraints

Total points: 200

All inputs have 1 ≤ K ≤ N ≤ 5000

Easy set (40 points): 1 ≤ N ≤ 100, 1 ≤ K ≤ 3.

Time Limit: 3 seconds

Memory Limit: 64 MB (Stack memory: 8MB)

SAMPLE INPUT

SAMPLE OUTPUT