Cho số nguyên dương ~n~ và gọi ~S~ là tập hợp các ước của ~n~. Cặp số ~(a,b)~ với ~a,b \in S~ có tính thứ tự được gọi là liên kết nếu như có thể chọn số nguyên dương ~k~ nào đó để cho ~a^k+b^k~ chia hết cho ~ab~. Chú ý: cặp số có thứ tự nghĩa là ~(a,b)~ và ~(b,a)~ được coi là phân biệt nhau. Yêu cầu đặt ra là tính số lượng cặp liên kết.

Gợi ý: hai số liên kết nhau thì tập hợp các ước nguyên tố của chúng có đặc điểm gì?

Input

Một dòng duy nhất gồm số nguyên dương ~n~ với ~1 \le n \le 10^{14}.~

Output

Đáp số của bài toán (cho biết rằng đáp số đó sẽ biểu diễn được trong kiểu Int64).

Sample input

4

Sample output

5

Giải thích Ở Ví dụ, với ~n=4~, ta có các cặp liên kết là ~(1,1),(2,2),(4,4),(2,4),(4,2)~ nên đáp số là ~5.~