B'This is the hard version of the problem. The only difference between the two versions is the constraint on n . You can make hacks only if both versions of the problem are solved. You are given an array of integers a of length n . In one operation, you will perform the following two-step process: Find the maximum number of times that you can perform the operation above. Each test contains multiple test cases. The first line of input contains a single integer t ( 1 <= t <= 100 ) -- the number of test cases. The description of the test cases follows. The first line of each test case contains a single integer n ( 1 <= n <= 800 ) -- the length of the array a . The second line of each test case contains n integers a_1, a_2, ldots, a_n ( 1 <= a_i <= n ) -- the elements of the array a . It is guaranteed that the sum of n over all test cases does not exceed 800 . For each test case, output a single integer -- the maximum number of times that you can perform the operation. In the first test case, one possible optimal sequence of operations is [ 1, 5, color{red}{3}, color{red}{2}, 4 ] rightarrow [ color{red}{1}, color{red}{5}, 4] rightarrow [4] . In the third test case, one possible optimal sequence of operations is [1, color{red}{2}, color{red}{3}] rightarrow [1] . '...