Given a number n (n <= 10^12) print all its prime factors in strictly ascending order. (Note each prime factor should be printed on a new line.)

Warning: Use long long int for taking input. Integer will overflow. The format specifier for long long int is %lld.

Example

Input:
60

Output:
2
3
5

Input:
100

Output:
2
5