\(2\) 이상의 자연수 \(N\)이 주어졌을 때, \(N\)을 소인수분해하는 프로그램을 작성하시오.

소인수분해 결과는 오름차순으로 정렬하여 한 줄에 하나씩 출력한다.

입력

첫째 줄에 자연수 \(N\)이 주어진다. (\(2 \le N \le 2^{40}\))

출력

\(N\)의 소인수를 오름차순으로 한 줄에 하나씩 출력한다.

예제 입력 1

72

예제 출력 1

2
2
2
3
3

예제 입력 2

999999999989

예제 출력 2

999999999989