소인수분해

자연수 N이 주어져요. N을 소인수분해해보세요.

입력

자연수 N이 주어져요.

• $2 \leq N \leq 2 \times 10^9$

출력

소인수를 오름차순으로 한 줄씩 출력하세요. 각 줄에는 소인수와 해당 소인수가 몇 번 곱해졌는지를 공백으로 구분하여 출력해요.