D - Together Square Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400 点

問題文

整数 N が与えられます。以下の条件を満たす N 以下の正整数の組 (i,j) の個数を求めてください。

  • i \times j は平方数である。

制約

  • 1 \le N \le 2 \times 10^5
  • N は整数である。

入力

入力は以下の形式で標準入力から与えられる。

N

出力

答えを出力せよ。

入力例 1

4

出力例 1

6

(1,1),(1,4),(2,2),(3,3),(4,1),(4,4) の 6 個が条件を満たします。

(2,3) は 2 \times 3 =6 が平方数でないため条件を満たしません。

入力例 2

254

出力例 2

896

Score : 400 points

Problem Statement

You are given an integer N. Find the number of pairs (i,j) of positive integers at most N that satisfy the following condition:

  • i \times j is a square number.

Constraints

  • 1 \le N \le 2 \times 10^5
  • N is an integer.

Input

Input is given from Standard Input in the following format:

N

Output

Print the answer.

Sample Input 1

4

Sample Output 1

6

The six pairs (1,1),(1,4),(2,2),(3,3),(4,1),(4,4) satisfy the condition.

On the other hand, (2,3) does not, since 2 \times 3 =6 is not a square number.

Sample Input 2

254

Sample Output 2

896