Problem Miguel și Tabelele


Cerința

Miguel are \(Q\) tabele (matrici) 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\):

masa

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\).

General info

ID: 71

Upload: AlexVasiluta

Input: Console Input

Memory limit: 64MB/16MB

Time limit: 1s

Author: Popa Sebastian

Source: Miguel's Summer Challenge

Submissions

Special Submissions