시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
15 초 256 MB 26 5 3 50.000%

문제

Little Tomato has a permutation P from 1 to n on a board. Each day, he swaps some numbers in P to form a new permutation P', and then tries to find the longest increasing subsequence (LIS) of P'. He believes that he can eventually find a faster algorithm for calculating LIS.

One day after an earthquake, some of the numbers in the permutation P has dropped off the board. Little tomato soon wondered, if he puts all the numbers back in a certain way, what will be the largest possible length of the LIS of the recovered permutation?

입력

First line of the input contains an integer T (1 ≤ T ≤ 100) denoting the number of the test cases. For each test case, the first line contains an integer n (1 ≤ n ≤ 105) indicating the length of the permutation. The next line contains a incomplete permutation a1, a2, ··· , an. If ai = 0, that means the number originally at the i-th position has dropped. The input will be always valid, and less than 10MB.

출력

For each test case, output the maximum possible length of the LIS of the recovered permutation.

예제 입력

4
5
0 0 0 0 0
10
1 2 3 4 0 0 0 0 9 10
14
1 0 3 0 5 0 7 0 9 0 11 0 13 0
9
3 0 0 0 7 8 9 0 0

예제 출력

5
10
14
7

힌트