Cerința

Pentru că ești iubitor de matematică ai organizat o petrecere unde inviți N numere naturale nenule. Ce coincidență, numere s-au așezat într-un vector iar acum trebuie să vezi pentru fiecare număr câte secvențe (elemente adiacente) îl conțin pe respectivul element și au cmmmdc-ul mai mare ca 1.

Date de intrare

Fișierul de intrare GCDP.in conține pe prima linie numărul N, iar pe a doua linie N numere naturale nenule separate prin spații.

Date de ieșire

Fișierul de ieșire GCDP.out va conține pe prima linie N numere naturale, al i-lea număr reprezenând răspunsul pentru cea de a i a valoare din vector.

Restricții și precizări

• 1 ≤ N ≤ 100.000
• numerele de pe a doua linie a fișierului de intrare vor fi mai mici sau egale cu 1.000.000.000.

Exemplu:

GCDP.in

3
2 6 3

GCDP.out

2 3 2

Explicație

Pentru prima valoare secvențele sunt [1,1] și [1,2].
Pentru a doua valoare secvențele sunt [1,2], [2,2] și [2,3].
Pentru a treia valoare secvențele sunt [2,3] și [3,3].