B"Alan Turing is standing on a tape divided into cells that is infinite in both directions. Cells are numbered with consecutive integers from left to right. Alan is initially standing in cell 0 . Every cell x has cell x - 1 on the left and cell x + 1 on the right. Each cell can either contain an integer or be empty. Initially all cells are empty. Alan is given a permutation a_1, a_2, ldots, a_n of integers from 1 to n that was chosen uniformly at random among all permutations of length n . At time 1 , integer a_1 is written down into cell 0 where Alan is located. At each time i from 2 to n inclusive, the following happens. First, Alan decides whether to stay in the same cell he's currently in, move to the neighboring cell on the left, or move to the neighboring cell on the right. After that, integer a_i is written down into the cell where Alan is located. If that cell already contained some integer, the old integer is overwritten and irrelevant from that moment on. Once a_n is written down into some cell at time n , sequence b of all integers contained in the cells from left to right is formed. Empty cells are ignored. Turing's award is equal to the length of the longest increasing subsequence of sequence b . Help Alan and determine the largest possible value of his award if he acts optimally. Each test contains multiple test cases. The first line contains the number of test cases t ( 1 <= t <= 1000 ). Description of the test cases follows. Each test case is given in two lines. The first line of each test case contains a single integer n ( 2 <= n <= 15 ,000 ) -- the length of the permutation given to Alan. The second line contains n distinct integers a_1, a_2, ldots, a_n ( 1 <= a_i <= n ) -- the elements of the permutation. It is guaranteed that the permutation was chosen uniformly at random among all pe"...