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

Để chuẩn bị cho lễ phát động kỳ thi Olympic Tin học 2023, ba bạn trong team Lina, Anna và Luna đã ngồi trang trí băng rôn bằng cách viết liên tiếp các ký tự ~O, L, P~ thành một dãy dài. Nhưng vì băng rôn hơi dài nên thầy lãnh đội Tina muốn cắt ra một đoạn nhỏ sao cho trong đoạn đó có một ký tự nào đó xuất hiện từ ~3~ lần trở lên. Bạn hãy giúp team đếm thử xem có bao nhiêu cách cắt như vậy nhé?

Input: một dòng duy nhất là chuỗi chứa các ký tự ~O, L, P~, mỗi ký tự có thể xuất hiện ~0~ hoặc nhiều lần. Độ dài chuỗi không vượt quá ~10^5.~

Output: đáp số của bài toán.

Sample input 1:

OLPOLP

Sample output 1:

0

Sample input 2:

OOOOO

Sample output 2:

6

Giải thích: trong VD1, ta thấy không có ký tự nào xuất hiện 3 lần trở lên nên đáp số là 0, còn trong VD2, ta có các cách chọn chuỗi con từ các cặp vị trí sau: ~(1,3),(1,4),(1,5),(2,4),(2,5),(3,5).~

Các đại pháp sư Trung Hoa trong CLB H3.2 đã sáng tạo ra một bảng hình chữ nhật ma thuật có kích thước ~n \times m~ (gồm ~n~ dòng và ~m~ cột), trên đó được điền các số nguyên dương. Những em SV K19, những thành viên mới của CLB muốn nhận được bí kíp của các đại pháp sư này thì phải chọn ra được bốn ô trong bảng thỏa mãn đồng thời các điều kiện sau:

• Bốn ô đó là đỉnh của hình chữ nhật có cạnh song song hoặc vuông góc với cạnh của bảng ban đầu.
• Trên bốn số điền trên bốn ô đó, có ít nhất ~75 \%~ là số chính phương.
• Người đi sau sẽ không được chọn trùng lại cả bốn ô của người đi trước.

Hỏi có tất cả bao nhiêu thành viên sẽ có thể nhận được bí kíp của các đại pháp sư?

Input

Dòng đầu tiên gồm số nguyên dương ~n, m~ với ~2 \le n, m \le 500.~ Trong các dòng tiếp theo là mô tả thông tin của bảng, mỗi số trên bảng là nguyên dương và không vượt quá ~10^9.~

Output

Số em SV may mắn.

Sample input

3 3
1 2 9
4 5 6
1 8 4

Sample output

3

Giải thích: có ba hình chữ nhật thỏa mãn với số trên các đỉnh là: ~(1,9,4,6)~, ~(4,6,1,4)~ và ~(1,9,1,4).~

Thầy Tina có ~n~ đoạn thẳng đánh số từ ~1,2,...,n~ có độ dài là các số nguyên dương không nhất thiết phân biệt. Thầy muốn chọn ra bốn đoạn thẳng trong số đó sao cho tạo được một hình bình hành. Hỏi thầy Tina có bao nhiêu cách?

Input

Dòng đầu tiên gồm số nguyên dương ~n~ với ~4 \le n \le 10^5.~ Dòng tiếp theo gồm ~n~ số nguyên dương không vượt quá ~10^6.~

Output

Số cách chọn cần tìm.

Sample input

6
1 1 1 1 2 2

Sample output

7

Giải thích: hình bình hành thì có các cặp cạnh đối bằng nhau, vì thế ta cần chọn ra hai cặp số bằng nhau (nếu cả bốn số bằng nhau luôn cũng được). Như thế ta có thể chọn bốn đoạn độ dài ~1~ với ~1~ cách hoặc chọn ~2~ đoạn độ dài ~1~ đi cùng với ~2~ đoạn độ dài ~2~, có ~6~ cách, tổng cộng là ~1+6=7~ cách.

Ghi chú: bài này với test lớn thì tính toán có thể sẽ ra giá trị vượt ngưỡng Int64, ta cần dùng Python hoặc có cách xử lý khéo léo mới giải quyết được trọn vẹn.

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

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

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.