Dulaj’s Dilemma

Dulaj is working as the coordinator of NOI Monthly Contests and he is responsible for choosing the problem-setters. Since everyone is busy these days, he decides to pair the candidates up to speed things up, and also he makes sure that every team has an equal total skill level to make it fair. This aside, he also wants to make the maximum number of teams possible because he was busy watching Squid Game and now the competition is only days away, so he needs all the help he can get. Due to his load of work, he assigns this task to you. Eager to impress him, you don’t hesitate and agree.

There are N number of problem-setters and each problem-setter is assigned with an integer that represents their problem-setting abilities. You are tasked with finding the maximum number of teams, that can be formed such that every team has the same total skill level. The total skill level of a team is the sum of skill levels of both team members.

Input Format

• The first line contains a single integer T denoting the number of test cases.
• For each test case there are two lines,
  • First line contains a single integer N denoting the number of problem-setters.
  • Second line contains N number of space separated integers, corresponding to the array S where S_i denotes the skill level of the i^th problem-setter.

Output Format

• For each test case, print the maximum number of teams that can be formed such that the total skill level of each team is the same.

Constraints

• 1 \(\leq\) T \(\leq\) 1000
• 1 \(\leq\) N \(\leq\) 50
• 1 \(\leq\) S_i \(\leq\) N

Sample Input 0

4
2
1 2
5
1 1 1 1 1
6
1 2 3 4 5 6
4
3 4 3 3

Sample Output 0

1
2
3
1