Alam has an array with elements and an integer .
For each index and are neighbours. But recently index had a quarrel with his neighbour . So they are not neighbour anymore.
Alam loves Longest Increasing subsequences and wants the Longest Increasing subsequence of the array to be as long as possible.
You have a special power. You can swap any two values of the array if they are neighbors.
So, help Alam find his Longest increasing subsequence of the array using your special power zero or more number of times.
First line contains a single integer the number of test cases.
Each test case starts with two integers and and the number of element of the array and the integer describe in the problem statement.
Next line contains space separated integers the elements of the array.
It is guaranteed that the sum of all in over all test cases will not exceed and all the elements of array will fit into a 32 bit signed integer.
For each test case print a single integer the length of the longest increasing subsequence of the array after using you special power zero or more amount of times.
Input | Output |
---|---|
2 3 1 1 2 3 4 2 2 2 5 4 | 3 4 |