Longest Subsequence with Adjacent Difference at Most 1

Given a list of ( N ) integers, your task is to find the length of the longest subsequence such that for every two adjacent elements ( s_i ) and ( s_{i+1} ) in the subsequence, the absolute difference satisfies ( |s_i - s_{i+1}| \le 1 ). Note that a subsequence is derived from the original list by deleting some or no elements without changing the order of the remaining elements.

One way to solve the problem is to observe that the best subsequence can be constructed by choosing all occurrences of some integer ( x ) together with all occurrences of ( x+1 ) (or ( x-1 )). This is because the maximum frequency you can achieve while meeting the condition is simply the sum of counts of two consecutive numbers.

Example: Consider the list: [1, 2, 2, 3, 1, 2]. One optimal subsequence is [1, 2, 2, 1, 2] which has a length of 5 since for each adjacent pair the difference is ( \le 1 ).

inputFormat

The input is read from stdin and formatted as follows:

• The first line contains an integer ( T ), the number of test cases.
• Each test case consists of two lines:
  • The first line contains an integer ( N ), the number of elements in the array.
  • The second line contains ( N ) space-separated integers representing the array elements.

outputFormat

For each test case, print a single line containing one integer: the length of the longest subsequence satisfying ( |s_i - s_{i+1}| \le 1 ). The output for multiple test cases should follow the same order as the input test cases.## sample

2
6
1 2 2 3 1 2
5
1 3 5 7 9

5
1