Chef has an array A of length N.

He calls an index i (1 ≤ i ≤ N) *good* if there exists some j \neq i such that A_{i} = A_{j}.

Chef can perform the following operation at most once:

Choose any [subsequence] of the array A and add any positive integer to all the elements of the chosen subsequence.

Determine the maximum number of good indices Chef can get.

------ Input Format ------ 

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of two lines of input.
- The first line of each test case contains a single integer N denoting the length of the array A.
- The second line contains N space-separated integers denoting the array A.

------ Output Format ------ 

For each test case, output the maximum number of good indices Chef can get after performing the given operation at most once.

------ Constraints ------ 

$1 ≤ T ≤ 500$
$2 ≤ N ≤ 1000$
$1 ≤ A_{i} ≤ 1000$
- The sum of $N$ over all test cases won't exceed $2000$.

----- Sample Input 1 ------ 
3
6
1 3 5 2 4 8
4
2 3 4 5
7
1 1 2 2 3 4 4

----- Sample Output 1 ------ 
4
4
7

Difficulty: VERY_HARD
Tags: Dynamic programming

Greedy algorithms
Skill types: Dynamic programming

Greedy algorithms

Starter code:

Solutions:
def soln(A):
	freq = {}
	for i in A:
		if i in freq.keys():
			freq[i] += 1
		else:
			freq[i] = 1
	A = [*freq.keys()]
	A.sort()
	max_count = sum((freq[x] for x in freq if freq[x] > 1))
	for x in range(1, A[-1] - A[0] + 1):
		(s, p, count) = ([], {}, 0)
		for i in A:
			if i - x in freq:
				p[i] = p[i - x]
			else:
				p[i] = len(s)
				s.append([])
			s[p[i]].append(freq[i])
		for v in s:
			count += sum(v)
			v.sort()
			if len(v) & 1 and v[-1] == 1:
				count -= 1
		max_count = max(max_count, count)
	return max_count
for _ in range(int(input())):
	n = int(input())
	A = list(map(int, input().split()))
	print(soln(A))


for _ in range(int(input())):
	N = int(input())
	A = [*map(int, input().split())]
	freq = [0] * 1001
	for x in A:
		freq[x] += 1
	D = {}
	for i in range(1001):
		if freq[i]:
			D[i] = freq[i]
	ans = sum((D[x] for x in D if D[x] > 1))
	for x in range(1, 1001):
		(s, p, curr) = ([], {}, 0)
		for i in D:
			if i - x in D:
				p[i] = p[i - x]
			else:
				p[i] = len(s)
				s.append([])
			s[p[i]].append(D[i])
		for v in s:
			curr += sum(v)
			v.sort()
			if len(v) & 1 and v[-1] == 1:
				curr -= 1
		ans = max(curr, ans)
	print(ans)


for _ in range(int(input())):
	n = int(input())
	a = sorted(list(map(int, input().split())))
	freq = [0] * 1001
	for x in a:
		freq[x] += 1
	ans = 0
	for d in range(1, 1001):
		cur = 0
		mark = [0] * 1001
		for x in a:
			if mark[x] == 1:
				continue
			ptr = x
			tot = 0
			mx = 0
			while ptr <= 1000:
				if freq[ptr] == 0:
					break
				mark[ptr] = 1
				tot += freq[ptr]
				mx = max(mx, freq[ptr])
				ptr += d
			if mx > 1 or tot % 2 == 0:
				cur += tot
			else:
				cur += tot - 1
		ans = max(ans, cur)
	print(ans)


for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	a.sort()
	freq = [0] * 1001
	ans = 0
	for x in a:
		freq[x] += 1
	for d in range(1, 1001):
		mark = [0] * 1001
		Ans = 0
		for x in a:
			pointer = x
			if mark[pointer] == 1:
				continue
			mx = 0
			curAns = 0
			while pointer <= 1000:
				if freq[pointer] == 0:
					break
				mark[pointer] = 1
				curAns += freq[pointer]
				mx = max(mx, freq[pointer])
				pointer += d
			if curAns % 2 == 0 or mx > 1:
				Ans += curAns
			else:
				Ans += curAns - 1
		ans = max(ans, Ans)
	print(ans)