ADABLOOM - Ada and Bloom

no tags 

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 Ai < Ai Aj < Aj (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 < Ai ≤ 1018, 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

hide comments
wisfaq: 2017-08-26 22:06:50

Thanks, Miloslav.

Last edit: 2017-08-26 22:14:18
morass: 2017-08-25 23:23:26

@wisfaq: Try to submit again (in pypy - it is faster) ... I've increased Time-Limit drasticali so it shall pass now (I guess). Your algo shall be right, yet python seems to be very slow :'(

morass: 2017-08-25 01:07:09

@wisfaq: One integer only - thank you - I'll update

wisfaq: 2017-08-24 13:56:58

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


Added by:Morass
Date:2017-08-24
Time limit:7s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All