Đức Tài là một đại gia angel investor của công ty IUHCoder. Cty này có ~n > 1~ thành viên và trong tháng tới, có 2 dự án cần hoàn thành. Để khuyến khích cho công việc, đại gia đã mang đến 2 túi vàng, mỗi túi có ~n~ đồng vàng để phát cho các thành viên trong dự án. Trong dự án 1, đại gia dự kiến sẽ thưởng cho top ~x~ nhân viên xuất sắc nhất trong cty, mỗi người một số tiền giống nhau. Cũng tương tự với dự án 2, đại gia thưởng cho top ~y~ nhân viên xuất sắc nhất trong cty, mỗi người một số tiền giống nhau trong đó ~x \neq y~. Đại gia thắc mắc là nên chọn ~x, y~ thế nào để chênh lệch tiền thưởng giữa hai lần là ít nhất, hãy giúp đại gia tính ra con số đó nhé. Ngày xưa đại gia cũng code giỏi lắm nhưng từ lúc lo kinh doanh thì bỏ code hẳn rồi.

Input

Một số nguyên dương duy nhất là ~n~ với ~2 \le n \le 10^{14}.~

Output

Chênh lệch tiền thưởng ít nhất.

Sample input 1

15

Sample output 1

2

Sample input 2

100

Sample output 2

1

Giải thích: trong VD1, ta có thể chọn ~(x,y)=(3,5)~ thì số tiền thưởng lần lượt là ~5,3~ với chênh lệch là ~2.~ Còn trong VD2, ta có thể chọn ~(x,y)=(25,20)~ thì số tiền thưởng lần lượt là ~4,5~ với chênh lệch là ~1.~

Cho số nguyên dương ~n~ có tập hợp các ước nguyên tố là ~A~, hỏi có bao nhiêu số chính phương không vượt quá ~n~ mà tập ước nguyên tố của nó là tập con của ~A~?

Input

Số nguyên dương ~n~ với ~1 \le n \le 10^{14}.~

Output

Số lượng cần tìm.

Sample input

36

Sample output

5

Giải thích: các số thỏa mãn là ~1, 4, 9, 16, 36~.

Để chuẩn bị cho kỳ thi Olympic, nhóm bạn NaTaLo đã luyện rất nhiều về công thức tính tổng các ước của một số nguyên dương, đến nỗi trong giấc mơ, bạn gặp một ác mộng như sau: Ban tổ chức cho các bạn một con số nguyên dương, chính là điểm kinh nghiệm của các bạn ấy hiện tại (tính theo đơn vị EXP). Các bạn cần tính tổng các ước số dương của số đó để được số mới (chú ý rằng nếu ~a~ chia hết cho ~b~ thì ~b~ là một ước của ~a~), có thể xem là kỹ năng của các bạn ấy tích lũy được sau mỗi năm là bao nhiêu. Cứ làm như thế nhiều lần cho đến khi nào đạt được level đủ để tham gia Siêu cúp, tức là một ngàn tỷ EXP, thì mới thôi! Các bạn tính xong và giật mình với số năm đó, hãy cùng các bạn ấy trải nghiệm nỗi sợ đó nhé.

Input

Một dòng là số nguyên dương ~n~ với ~1 \le n \le 10^{12}~ cho biết điểm kinh nghiệm của nhóm bạn hiện tại.

Output

Một số nguyên duy nhất là đáp số của bài toán (cho biết rằng giá trị này vẫn tính được trong kiểu Int64). Nếu không thực hiện được thì in ra ~-1.~

Sample input 1

999999999999

Sample output 1

1

Sample input 2

2

Sample output 2

28

Trong Ví dụ 1, các bạn ấy chỉ cần tốn một năm là đạt được; còn trong Ví dụ 2, các bạn ấy còn phải luyện thêm gần ~30~ năm: ~2 \to 3 \to 4 \to 7 \to 8 \to 15 \to ...~ giấc mơ Siêu cúp còn hơi xa xôi.

Anh Mạnh là chuyên gia số học của CLB H3.2, cụ thể là về mảng tử vi lý số, coi bói đoán đường tình duyên. Vào một ngày gặp gỡ các bé K19, Mạnh đã cho một team ICPC ba người xem thử tài nghệ bói toán của mình. Mạnh cho các bạn này một số nguyên dương ~n~ rồi yêu cầu mỗi người chọn ra một ước dương tùy ý của ~n~, các ước phải phân biệt nhau sao cho tổng các số của hai bạn bất kỳ đều phải chẵn. Dựa vào các ước số đó, Mạnh có thể luận ra được nhiều quẻ rất hay, chẳng hạn bói xem có hai người nào đó cùng team là yêu nhau hay không, hay người team này yêu team khác, ... nói chung có nhiều chuyện để bói. Nhưng trước hết, bạn hãy giúp team này đếm xem có bao nhiêu cách chọn các bộ ba như thế nhé?

Input

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

Output

Số bộ ba cần tìm.

Sample input

15

Sample output

4

Giải thích: ta thấy số ~15~ có các ước là ~1,3,5,15~, ta chọn ra ba số tùy ý trong đó thì đều thỏa mãn, chẳng hạn chọn ~(1,3,5)~ thì tổng của các cặp số sẽ là ~4,8,6~ đều chẵn. Số lượng bộ ba cần tìm là ~4.~ Chú ý nếu không có bộ nào thỏa thì in ra ~0~.

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.~

Biết rằng một số nguyên dương ~n~ nào đó không phải là lũy thừa ~2~ và có ~m~ ước dương. Hỏi số ~2n~ có ít nhất mấy ước dương?

Input

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

Output

Số ước ít nhất có thể có của ~2n~.

Sample input 1

3

Sample output 1

6

Sample input 2

15

Sample output 2

18

Giải thích: trong VD1, theo công thức tính số ước, ta thấy số ~n~ có thể có dạng ~p^2~ với ~p~ lẻ nên ~2n=2p^2~ sẽ có số ước là 6. Ở VD2, số ~n~ có thể có dạng ~p^{14}~ hoặc ~2^2.p^4~ hoặc ~2^4.p^2~ với ~p~ là số nguyên tố lẻ; tương ứng thì số ~2n~ có số lượng ước dương là ~30,20,18~ nên giá trị nhỏ nhất cần tìm là ~18.~

Bạn Tài và Lộc đang đi coi thầy phong thuỷ để xin quẻ cho một start up công nghệ. Năm trước, hai bạn đã khai trương và xin được một số phong thuỷ là ~n~ nhưng công ty vẫn còn nhiều khó khăn. Lần nay, thầy phong thuỷ phán rằng mỗi số ~n~ là chưa đủ mà hai bạn cần phải chi tiền ra xin thêm vài số nữa về dán thêm vào trong văn phong thì công ty sẽ ăn nên làm ra được. Các số đó, đặt là ~m~, có đặc điểm như sau:

• Đó là các số nguyên dương có giá trị không vượt quá ~n~;
• Là bình phương đúng hoặc lập phương đúng (tức là tồn tại ~x~ nguyên để ~m=x^2~ hoặc ~m=x^3~);
• Mỗi ước nguyên tố (nếu có) của ~m~ thì cũng là ước của ~n~?

Hãy giúp bạn Tài và Lộc tính xem họ cần dán bao nhiêu số theo lời thầy phong thuỷ nhé.

Input

Số nguyên dương ~n~ với ~1 \le n \le 10^{14}.~

Output

Số lượng số đặc biệt cần dán.

Sample input

36

Sample output

7

Giải thích.

Trong ví dụ đã cho, các số thỏa mãn là ~1, 4, 8, 9, 16, 27, 36~. Chú ý rằng số ~1~ vì không có ước nguyên tố nào nên tập ước nguyên tố của nó là tập rỗng, và cũng thoả mãn điều kiện.