Problem Killer

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 65536/65536 K (Java/Others)

Description

You are a "Problem Killer", you want to solve many problems.
Now you have $n$ problems, the $i$-th problem's difficulty is represented by an integer $a_i$ ($1 \le a_i \le 10^{9}$).
For some strange reason, you must choose some integer $l$ and $r$ ($1 \le l \le r \le n$), and solve the problems between the $l$-th and the $r$-th, and these problems' difficulties must form an AP (Arithmetic Progression) or a GP (Geometric Progression).
So how many problems can you solve at most?

You can find the definitions of AP and GP by the following links:
https://en.wikipedia.org/wiki/Arithmetic_progression
https://en.wikipedia.org/wiki/Geometric_progression

Input

The first line contains a single integer $T$, indicating the number of cases.
For each test case, the first line contains a single integer $n$, the second line contains $n$ integers $a_1, a_2, \cdots, a_n$.

$T \le 10^4, \sum n \le 10^6$

Output

For each test case, output one line with a single integer, representing the answer.

Sample Input

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

Sample Output

4 6

Hint

wange2014

Source

2015 Multi-University Training Contest 4

提交代码