Call an array (b) of size (m) good if the following conditions hold: (1 \leq b_i \leq i) for each (1 \leq i \leq m). There exists a permutation(^{\text{∗}}) (p) of size (m) such that for each (1 \leq i \leq m), (b_i) is the smallest integer where (\min(p_{b_i}, p_{b_i+1}, \ldots, p_i)=p_i). For example, the array (1,1,3,3,5) is good (where the permutation (p=2,1,5,3,4) satisfies the second requirement), but the array (1,1,2) isn't. Note the empty array is considered to be good . You are given an array (a) of size (n). Find the length of the longest good subsequence(^{\text{†}}) of (a). (^{\text{∗}})A permutation of length (m) is an array consisting of (m) distinct integers from (1) to (m) in arbitrary order. For example, (2,3,1,5,4) is a permutation, but (1,2,2) is not a permutation ((2) appears twice in the array), and (1,3,4) is also not a permutation ((m=3) but there is (4) in the array). (^{\text{†}})A sequence (c) is a subsequence of a sequence (d) if (c) can be obtained from (d) by the deletion of several (possibly, zero or all) element from arbitrary positions. Each test contains multiple test cases. The first line contains the number of test cases (t) ((1 \le t \le 10^4)). The description of the test cases follows. The first line of each test case contains an integer (n) ((1 \leq n \leq 15\,000)) – the length of (a). The second line of each test case contains (n) integers (a_1,a_2,\ldots,a_n) ((1 \leq a_i \leq n)) — denoting the array (a). It is guaranteed that the sum of (n^2) does not exceed (15\,000^2) over all test cases. For each test case, output the length of the longest good subsequence of (a) on a new line. In the first test case, the entire sequence is good . In the second test case, the longest good subsequence is (1,2).