MATH - Tích các thừa số nguyên tố
Point:
100.0
Time limit:
1.0s
Memory limit:
500 Mb
Input:
standard input
Output:
standard output
Tác giả:  
Loại đề bài

Cho số nguyên dương N(2≤N≤109N (2 \le N \le 10^9) , hãy phân tích NN ra tích các thừa số nguyên tố.

Input

  • Một dòng duy nhất chứa số n.

Output

  • Mỗi dòng ghi một thừa số nguyên tố và số mũ tương ứng cách nhau bởi dấu cách.
  • Các thừa số nguyên tố in ra theo thứ tự tăng dần.

Example

INPUT OUTPUT GIẢI THÍCH
44 22 22 4=224 = 2^2
168168 22 33
33 11
77 11		 168=23∗31∗71168 = 2^3 * 3^1 * 7^1