POLSKI SPOJ

Ciąg EKG

Ciąg EKG to ciąg liczb całkowitych dodatnich zdefiniowany następująco: pierwsze dwa wyrazy ciągu to 1, 2, a każdy następny wyraz jest najmniejszą liczbą całkowitą dodatnią, która do tej pory nie wystąpiła w ciągu i która nie jest względnie pierwsza z wyrazem bezpośrednio poprzedzającym. Poniżej kilka początkowych wyrazów ciągu:

        1, 2, 4, 6, 3, 9, 12, 8, 10, 5, 15, 18, 14, 7, 21, 24, 16

Ciąg ten nazywany jest ciągiem EKG, ponieważ jego wykres przypomina elektrokardiogram. Ciąg ten ma tę własność, że wszystkie liczby całkowite dodatnie prędzej czy później pojawią się w nim. Twoim zadaniem jest wyznaczyć pozycję w ciągu dla danej liczby całkowitej.

Wejście
W pierwszym wierszu wejścia znajduje się liczba całkowita d (1 ≤ d ≤ 1000) oznaczająca liczbę przypadków testowych. Każdy przypadek testowy to jedna liczba całkowita a (1 ≤ a ≤ 3 · 10⁵).

Wyjście
Dla każdej liczby podanej na wejściu należy wyznaczyć jej pozycję porządkową w ciągu EKG.

Przykład

Wejście
5
1
2
3
10
15

Wyjście
1
2
5
9
11