subgeom

Miruna tocmai a învățat la ora de matematică despre progresii geometrice. Un șir de numere naturale nenule se numește progresie geometrică dacă este respectată una dintre următoarele două condiții:

• Șirul este format dintr-un singur element.
• Dacă șirul este format din $N (N \gt 1)$ elemente $v_1, v_2, \dots, v_N$, atunci există un număr întreg $K$ mai mare strict decât $1$ astfel încât raportul oricăror două elemente consecutive din șir este egal cu $K$. Altfel spus, oricare ar fi un indice $i, 1 \leq i \lt N, v_{i+1} / v_i = K$.

Miruna are o imaginație bogată, așa că inventează o noțiune nemaîntâlnită până acum - cea de subșir geometric: dându-se un șir de numere naturale nenule, un subșir care este progresie geometrică se numește subșir geometric.

Cerință

Scrieţi un program care pentru un şir de $N$ elemente afişează lungimea celui mai lung subşir geometric al său.

Date de intrare

Fișierul de intrare subgeom.in va conține pe prima linie numărul natural $T$ reprezentând numărul de seturi de date din fișier. Fiecare dintre următoarele $T$ linii conține un set de date, sub forma:

$N \ v_1 \ v_2 \ \dots \ v_N$

Prima valoare este un număr natural $N$, reprezentând numărul de elemente din șir, urmat de cele $N$ numere naturale nenule ce alcătuiesc șirul, separate prin câte un spațiu.

Date de ieșire

Fișierul de ieșire subgeom.out va conține $T$ linii, câte o linie pentru fiecare set de date. Linia $i$ conține un număr natural reprezentând lungimea maximă a unui subșir geometric al șirului descris pe linia $i + 1$ în fișierul de intrare.

Restricții și precizări

• $1 \leq T \leq 10$
• $1 \leq N \leq 5 \ 000$
• Pentru $40\%$ din teste $1 \leq N \leq 128$
• Elementele șirului sunt numere naturale din intervalul $[1, 10^5]$
• Un subșir al unui șir $v_1, v_2, \dots , v_N$ este format din elemente ale șirului considerate în ordinea în care acestea apar în șir: $v_{i1}, v_{i2}, \dots, v_{ik} (1 \leq i1 \lt i2 \lt \dots \lt ik \leq N)$.

Exemplu

subgeom.in

6
3 5 3 7
3 8 4 2
3 4 4 4
3 5 1 10
4 1 2 3 9
5 6 2 8 6 18

subgeom.out

1
1
1
2
3
3

Explicație

Pentru primele trei teste toate subșirurile geometrice au lungimea $1$.

Pentru al patrulea test soluția este formată din subșirul $5, 10$.

Pentru al cincilea test soluția este formată din subșirul $1, 3, 9$.

Pentru ultimul test soluția este formată din subșirul $2, 6, 18$.