Lui Fibo îi plac numerele care nu se potrivesc perfect. Recent, acesta a descoperit niște numere mai speciale: el numește un număr x ca fiind antidivizorul unui număr natural nenul k, dacă x este cel mai mic număr natural nenul care nu-l divide pe k. Fie F(k) = x, unde x este antidivizorul lui k.

Cerința

Să se calculeze F(1) + F(2) + ... + F(N) pentru T valori ale lui N.

Date de intrare

Pe prima linie a fișierului de intrare antidivizor.in se va afla un număr natural T, care va reprezenta numărul de valori ale lui N. Pe fiecare dintre următoarele T linii se vor afla valorile naturale nenule ale lui N, câte una pe linie.

Date de ieșire

Fișierul de ieșire antidivizor.out va conține T linii. A i-a linie va conține un singur număr natural, acela fiind suma cerută pentru valoarea lui N aflată pe linia i+1 din fișierul de intrare.

Restricții și precizări

• 1 ≤ T ≤ 100.000
• 1 ≤ N ≤ 1015
• Pentru 35 de puncte, 1 ≤ N ≤ 1000, 1 ≤ T ≤ 100
• Pentru 26 de puncte, 1 ≤ N ≤ 1.000.000, 1 ≤ T ≤ 100.000
• Pentru 19 puncte, 1 ≤ N ≤ 1015, 1 ≤ T ≤ 100
• Pentru 20 de puncte, fără restricții suplimentare

Exemplul 1:

antidivizor.in

2
1
2

antidivizor.out

2
5

Explicație

F(1) = 2 deoarece 1 divide pe 1, dar 2 nu divide pe 1. F(2) = 3, deoarece 1 divide pe 2, 2 divide pe 2, dar 3 nu divide pe 2.

Exemplul 2:

antidivizor.in

4
2
3
4
10

antidivizor.out

5
7
10
26

Explicație

F(1) = 2
F(2) = 3
F(3) = 2
F(4) = 3
F(5) = 2
F(6) = 4
F(7) = 2
F(8) = 3
F(9) = 2
F(10) = 3