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ą1 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ą.