Longest Gear Chain

You are given n gears with various sizes. Two gears can mesh if the size of one gear is exactly twice that of another. Your task is to determine the length of the longest chain of meshing gears.

More formally, given a list of gear sizes gears (each an integer), you need to find the maximum value of chain(gear) where:

$$chain(gear) = \begin{cases} chain(gear/2) + 1, & \text{if } gear \text{ is even and } gear/2 \text{ exists in the list} \\ 1, & \text{otherwise} \end{cases} $$

Note: You must process multiple test cases from stdin and output the result of each test case to stdout on a separate line.

inputFormat

The input starts with an integer T indicating the number of test cases. Each test case consists of two lines:

• The first line of each test case contains an integer n (the number of gears).
• The second line contains n space-separated integers representing the sizes of the gears.

outputFormat

For each test case, output a single integer on a new line which is the length of the longest chain of gears that can mesh together.

## sample

3
5
1 2 4 3 8
6
6 3 12 24 48 96
7
1 2 4 8 16 32 64

4
6
7

</p>