Leo was really bored after finishing all of Project Euler, so he decided to create his own computational mathematics website: Project Feng! Here, he'll be able to enlighten the students of Massey with new computer science problems. For his first problem, Leo decides on something simple, but crucial:
The year has changed from to . Since the current year is often used in math contest problems, it's very helpful to know its prime factorization. Leo is a very diligent math student and already knows the prime factorization of . Use his information to write a program to find the prime factorization of , and, to save yourself time in the future, any other year.
One line containing the integer , the year to prime factorize.
On every line and in increasing order, print a prime factor of .