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>1) elemente v1 v2 ...vN, 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 ≤ i < N, vi+1/vi = 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 numeste 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 v1 v2 ...vN
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

1 ≤ T ≤ 10
1 ≤ N ≤ 5000
Pentru 40% din teste 1 ≤ N ≤ 128
Elementele şirului sunt numere naturale din intervalul [1, 105]
Un subşir al unui şir v1 v2 ...vN este format din elemente ale şirului considerate în ordinea în care acestea apar în şir: vi1 vi2... vik (1≤i1<i2<...<ik≤N).

Exemple

subgeom.in	subgeom.out	Explicaţii
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	1 1 1 2 3 3	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

autor: Stud. Andrei Grigorean

propunător: Prof. Emanuela Cerchez

Liceul de Informatica ″Grigore Moisil″

emanuela.cerchez@gmail.com