CF1335E1 Three Blocks Palindrome (easy version)

The only difference between easy and hard versions is constraints. You are given a sequence $ a $ consisting of $ n $ positive integers. Let's define a three blocks palindrome as the sequence, consisting of at most two distinct elements (let these elements are $ a $ and $ b $ , $ a $ can be equal $ b $ ) and is as follows: $ [\underbrace{a, a, \dots, a}_{x}, \underbrace{b, b, \dots, b}_{y}, \underbrace{a, a, \dots, a}_{x}] $ . There $ x, y $ are integers greater than or equal to $ 0 $ . For example, sequences $ [] $ , $ [2] $ , $ [1, 1] $ , $ [1, 2, 1] $ , $ [1, 2, 2, 1] $ and $ [1, 1, 2, 1, 1] $ are three block palindromes but $ [1, 2, 3, 2, 1] $ , $ [1, 2, 1, 2, 1] $ and $ [1, 2] $ are not. Your task is to choose the maximum by length subsequence of $ a $ that is a three blocks palindrome. You have to answer $ t $ independent test cases. Recall that the sequence $ t $ is a a subsequence of the sequence $ s $ if $ t $ can be derived from $ s $ by removing zero or more elements without changing the order of the remaining elements. For example, if $ s=[1, 2, 1, 3, 1, 2, 1] $ , then possible subsequences are: $ [1, 1, 1, 1] $ , $ [3] $ and $ [1, 2, 1, 3, 1, 2, 1] $ , but not $ [3, 2, 3] $ and $ [1, 1, 1, 1, 2] $ .

The first line of the input contains one integer $ t $ ( $ 1 \le t \le 2000 $ ) — the number of test cases. Then $ t $ test cases follow. The first line of the test case contains one integer $ n $ ( $ 1 \le n \le 2000 $ ) — the length of $ a $ . The second line of the test case contains $ n $ integers $ a_1, a_2, \dots, a_n $ ( $ 1 \le a_i \le 26 $ ), where $ a_i $ is the $ i $ -th element of $ a $ . Note that the maximum value of $ a_i $ can be up to $ 26 $ . It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2000 $ ( $ \sum n \le 2000 $ ).

For each test case, print the answer — the maximum possible length of some subsequence of $ a $ that is a three blocks palindrome.