Cerința

Miguel are $Q$ tabele (matrice) pătratice indexate de la 1. Fiecare element al unui tabel este egal cu $cmmdc$-ul indicilor. El vrea să știe câte valori egale cu 1 se află în total.

De exemplu, aceasta este un tabel de dimensiune $4$:

Date de intrare

Prima linie conține numărul de tabele $Q$. A doua linie conține $Q$ numere naturale, dimensiunile fiecărui tabel.

Date de ieșire

Se va afisa numărul total de valori egale cu 1.

Restricții și Precizări

• $1 \leq Q \leq 100000$;
• $0 \leq mărimea\ unui\ tabel \leq 1000000$;
• Dacă tabelul are dimensiunea $0$, atunci conține $0$ valori egale cu 1.
• $cmmdc$-ul a doua valori este cel mai mare divizor comun al acestor valori

Exemplu

stdin

3
1 3 4

stdout

19

Explicație

Tabelul de lungime $1$ conține $1$ valori egale cu $1$, tabelul cu lungime $3$ - $7$, iar tabelul cu lungime $4$ - $11$.