Cho số nguyên dương ~n~. Hãy phân tích ~n~ ra thừa số nguyên tố. Tức là tìm các số nguyên tố ~p_1, p_2, …, p_k~ đôi một phân biệt và các số nguyên dương ~α_1, α_2, …, α_k~ sao cho:$$n = {p_1}^{{\alpha _1}} \times {p_2}^{{\alpha _2}} \times ... \times {p_k}^{{\alpha _k}}$$

Input

• Gồm một dòng duy nhất chứa số nguyên dương ~n~.

Giới hạn:

• ~1 ≤ n ≤ 10^{12}~.

Output

• Dòng đầu ghi số nguyên dương ~k~
• ~k~ dòng sau, dòng thứ ~i~ ghi hai số ~p_i~ và ~α_i~ cách nhau một dấu cách, các số ~p_i~ được sắp xếp tăng dần.

Sample

Input #1

10

Output #1

2
2 1
5 1

Input #2

12

Output #2

2
2 2
3 1

Hint

• ~10 = 2^1 × 5^1~
• ~12 = 2^2 × 3^1~

Problem source: Chuyên Sơn La Online Judge