Разложение на простые множители - 2

По введённому числу N выведите его разложение на простые множители.

Входные данные

В единственной строке вводится единственное число N (2 ≤ N ≤ 100000).

Выходные данные

Выведите в каждой строке по два числа. Первое - делитель, второе - степень, с которой он входит в разложение числа. Если степень равна 0, то выводить делитель и степень не нужно. Пары чисел выводить по возрастанию делителя. Внимательно почитайте примеры.

Примеры