Description

Given a sequence A = a₁, a₂, ..., a_N.

A continuous subsequence A[L ... R] = a_L, ..., a_R of  A is called special if for every i, j in [L, R], a[ i ] * 2 ≠ a[ j ].

For example, if A = 3, 1, 4, 6, 2.

Then

• A[1, 3] = 3, 1, 4 is special.
• A[1, 4] = 3, 1, 4, 6 is not special because a[1] * 2 = a[4].
• A[2, 5] = 1, 4, 6, 2 is not special because a[5] * 2 = a[3] and a[2] * 2 = a[5].

 

Please find the maximum length of every special contiguous subsequence of A.

 

Input

The first line of the input contains a number T — the number of test cases.

The first line of each test case contains a positive integer N — the length of A.

The second line of each test case contains N positive integers — a₁, a₂, ..., a_N.

 

For each test,

1. T ≤ 10, N ≤ 10³, a_i ≤ 10⁹ 
2. T ≤ 10, N ≤ 10³, a_i ≤ 10⁹ 
3. T ≤ 10, N ≤ 10³, a_i ≤ 10⁹ 
4. T ≤ 10, N ≤ 10⁵, a_i ≤ 10⁹ 
5. T ≤ 10, N ≤ 10⁵, a_i ≤ 10⁹ 
6. T ≤ 10, N ≤ 10⁵, a_i ≤ 10⁹ 

 

Output

For each test case, print the maximum length of special contiguous subsequence.

 

Sample Input  Download

Sample Output  Download

Tags

Discuss