Number of Divisors 1

配点 : $300$ 点

問題文

正の整数 $N$ が与えられます。整数 $x$ $(1 ≦ x ≦ N)$ に対して $d(x)$ を次のように定義します．

• $d(x) := x$ の約数の個数

例えば，$d(1) = 1, d(6) = 4$ です．

$d(x) \times d(y)$ が偶数となるペア $(x, y)$ $(1 \leq x < y \leq N)$ の個数を求めてください．

制約

• 入力は全て整数
• $2 \leq N \leq 10^6$

入力

入力は以下の形式で標準入力から与えられます．

出力

答えを出力してください．

サンプル 1

3

3

$d(1) = 1, d(2) = 2, d(3) = 2$ より，以下のように計算できます．

• $d(1) \times d(2) = 2$
• $d(1) \times d(3) = 2$
• $d(2) \times d(3) = 4$

これらはすべて偶数なので求める個数は $3$ です．

サンプル 2

6

14

サンプル 3

1000000

499999000500

答えは $32$ bit 整数型に収まらない可能性があるので注意してください．