Odległość

Limit pamięci: 128 MB

W tym zadaniu rozważamy odległość między dodatnimi liczbami całkowitymi, zdefiniowaną w następujący sposób. Przez pojedynczą operację rozumiemy pomnożenie danej liczby przez liczbę pierwszą¹ lub podzielenie jej przez liczbę pierwszą (o ile dzieli się ona bez reszty). Odległość między liczbami i , oznaczana , to minimalna liczba operacji potrzebnych do przekształcenia liczby w liczbę . Na przykład, .

Zauważmy, że faktycznie funkcja ma cechy odległości - dla dowolnych dodatnich liczb całkowitych , i zachodzi:

• odległość liczby od niej samej wynosi 0: ,
• odległość od do jest taka sama, jak od do : , oraz
• spełniona jest nierówność trójkąta: .

Wejście

W pierwszym wierszu standardowego wejścia znajduje się jedna liczba całkowita (). W kolejnych wierszach znajdują się liczby (), po jednej w wierszu.

W testach wartych łącznie 30% punktów zachodzi dodatkowy warunek .

Wyjście

Twój program powinien wypisać na standardowe wyjście dokładnie wierszy, a w każdym z nich po jednej liczbie całkowitej. W -tym wierszu należy wypisać najmniejsze takie , że: , oraz jest minimalne.

Przykład

Dla danych wejściowych:

6
1
2
3
4
5
6

poprawną odpowiedzią jest:

2
1
1
2
1
2

Autor zadania: Wojciech Śmietanka.

1. Przypomnijmy, że liczba pierwsza to taka liczba całkowita dodatnia, która ma dokładnie dwa różne dzielniki: jedynkę i siebie samą.