subgeom

Subgeom

== include(page="template/taskheader" task_id="subgeom") ==

Poveste si cerinta...

Miruna tocmai a invatat la ora de matematica despre progresii geometrice. Un sir de numere naturale nenule se numeste progresie geometrica daca este respectata una dintre urmatoarele doua conditii:
 
* Sirul este format dintr-un singur element.
* Daca sirul este format din $N$ $(N > 1)$ elemente $v{~1~}, v{~2~}, ..., v{~N~}$, atunci exista un numar intreg $K$ mai mare strict decat $1$ astfel incat raportul oricaror doua elemente consecutive din sir este egal cu $K$. Altfel spus, oricare ar fi un indice $i$, $1 &le; i < N, v{~i+1~} / v{~i~} = K$.
 
Miruna are o imaginatie bogata, asa ca inventeaza o notiune nemaintalnita pana acum - cea de subsir geometric: dandu-se un sir de numere naturale nenule, un subsir care este progresie geometrica se numeste subsir geometric.
 
h2. Cerinta
 
Scrieti un program care pentru un sir de $N$ elemente afiseaza lungimea celui mai lung subsir geometric al sau.

h2. Date de intrare

Fisierul de intrare $subgeom.in$ ...

Fisierul de intrare $subgeom.in$ va contine pe prima linie numarul natural $T$ reprezentand numarul de seturi de date din fisier. Fiecare dintre urmatoarele $T$ linii contine un set de date, sub forma:
 
$N v{~1~} v{~2~} ... v{~N~}$
 
Prima valoare este un numar natural $N$, reprezentand numarul de elemente din sir, urmat de cele $N$ numere naturale nenule ce alcatuiesc sirul, separate prin cate un spatiu.

h2. Date de iesire

In fisierul de iesire $subgeom.out$ ...

Fisierul de iesire $subgeom.out$ va contine $T$ linii, cate o linie pentru fiecare set de date. Linia $i$ contine un numar natural reprezentand lungimea maxima a unui subsir geometric al sirului descris pe linia $i + 1$ in fisierul de intrare.

h2. Restrictii

h2. Restrictii si precizari

* $... ≤ ... ≤ ...$

* $1 ≤ T ≤ 10$
* $1 ≤ N ≤ 5000$
* Pentru $40%$ din teste $1 ≤ N ≤ 128$
* Elementele sirului sunt numere naturale din intervalul $[1, 10^5^]$
* Un subsir al unui sir $v{~1~} v{~2~} ...v{~N~}$ este format din elemente ale sirului considerate in ordinea in care acestea apar in sir: $v{~i1~} v{~i2~}... v{~ik~} (1 &le; i1 < i2 < ... < ik &le; N)$.

h2. Exemplu
table(example). |_. subgeom.in |_. subgeom.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 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

|
h3. Explicatie

...

Pentru primele trei teste toate subsirurile geometrice au lungimea $1$.
 
Pentru al patrulea test solutia este formata din subsirul $5, 10$.
 
Pentru al cincilea test solutia este formata din subsirul $1, 3, 9$.
 
Pentru ultimul test solutia este formata din subsirul $2, 6, 18$.

== include(page="template/taskfooter" task_id="subgeom") ==

3077