Problem Killer

Time Limit
1s
Memory Limit
65536KB
Judge Program
Standard
Ratio(Solve/Submit)
66.67%(2/3)
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 ai (1≤ai≤10^9).
For some strange reason, you must choose some integer l and r (1≤l≤r≤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 a1,a2,⋯,an.

T≤10^4,∑n≤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
Source:

2015 Multi-University Training Contest 4


Submit