As you might already know, Ada the Ladybug is a farmer. She grows many beautiful flowers. Each of the flowers has something called "blooming value". As long as A_i < A_i ⊕ A_j < A_j (where ⊕ stands for binary XOR, and A stands for "blooming value") is true for any pair of flowers (in any order), then those flowers-pair might bloom into a wonderful blossom, if they are replanted into same box (at most 2 flowers can be put into one box).

Ada wants to maximize the number of blossoms - can you find it?

Input

The first line of input containt 1 ≤ T ≤ 500 test-cases.

The first line of each test-case contains N 1 ≤ N ≤ 5000

The next line contains N integers 0 < A_i ≤ 10¹⁸, the blooming value of flower.

NOTE: The number of test-cases varies depending on size of array (the longest array won't be a single file more than once).

Output

For each test-cases, print the maximal number of blossoms Ada can achieve.

Example Input 1

6
7
8 5 4 8 4 9 11
6
9 9 12 12 4 6
3
7 7 4
4
10 6 9 1
8
11 4 12 3 1 2 1 10
4
12 2 5 2

Example Output 1

0
2
0
1
4
1

All possible pairs 1

Test-case 1:
Test-case 2:
4 < 8 < 12
4 < 8 < 12
6 < 10 < 12
6 < 10 < 12
Test-case 3:
Test-case 4:
1 < 8 < 9
Test-case 5:
1 < 2 < 3
1 < 10 < 11
1 < 2 < 3
1 < 10 < 11
2 < 8 < 10
2 < 9 < 11
3 < 9 < 10
3 < 8 < 11
4 < 8 < 12
Test-case 6:
5 < 9 < 12

Example Input 2

1
20
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

Example Output 3

7