Cho số nguyên dương \(n\). Hãy tìm bộ ba \((a,b,c)\) với \((1 ≤ a < b < c ≤ n)\) sao cho \(a×b, b×c, a×c\) đều là số chính phương.

Input

• Gồm mộ dòng chứa sô nguyên \(n(n ≤ 5.10^6 )\).

Output

• In ra một dòng là số lượng bộ ba \((a,b,c)\) tìm dược.

Ràng buộc

• Subtask 1: \(n ≤ 100\)

• Subtask 1: \(n ≤ 5000\)

• Subtask 3: \(n ≤ 10^5\)

• Subtask 4: \(n ≤ 5.10^6\)

Sample Input

20

Sample Output

5

Giải thích

• c1Có 5 bộ đó là (1,4,9), (1,4,16),(1,9,16),(2,8,18),(4,9,16)