Let's call an integer sequence beautiful if the following conditions hold: for every element except the first one, there is an element to the left less than it; for every element except the last one, there is an element to the right larger than it; For example, (1, 2), (42), (1, 4, 2, 4, 7), and (1, 2, 4, 8) are beautiful, but (2, 2, 4) and (1, 3, 5, 3) are not. Recall that a subsequence is a sequence that can be obtained from another sequence by removing some elements (possibly zero) without changing the order of the remaining elements. You are given an integer array (a) of size (n). Find the longest beautiful subsequence of the array (a) and print its length. The first line contains one integer (t) ((1 \le t \le 10^4)) — the number of test cases. Next, (t) independent cases follow. The first line of each test case contains a single integer (n) ((1 \le n \le 5 \cdot 10^5)) — the length of array (a). The second line of each test case contains (n) integers (a_1, a_2, \dots, a_n) ((1 \le a_i \le 10^6)) – the array (a). Additional constraint on the input: the total sum of (n) over all test cases doesn't exceed (5 \cdot 10^5). For each test case, print one integer — the length of the longest beautiful subsequence of array (a).