#P2671. Calc

    ID: 1728 传统题 1000ms 128MiB 尝试: 722 已通过: 286 难度: 7 上传者: 标签>CF2300提高+/省选-双射计数整除分块莫比乌斯反演交换求和顺序线性筛倍数枚举

Calc

Given an integer NN, count the number of pairs (a,b)(a, b) that satisfy the following conditions:

  1. 1≤a<b≤N1 \leq a < b \leq N
  2. a+ba + b divides a×ba \times b

Input Format

A single line containing the integer NN.

Output Format

A single line containing an integer representing the number of pairs (a,b)(a, b) that meet the conditions.

Example

Input:

15

Output:

4

Notes

Data scale and conditions:

  • test1: N≤5×107\text{test1: } N \leq 5 \times 10^7
  • test2: N≤108\text{test2: } N \leq 10^8
  • test3: N≤2×108\text{test3: } N \leq 2 \times 10^8
  • test4: N≤3×108\text{test4: } N \leq 3 \times 10^8
  • test5: N≤5×108\text{test5: } N \leq 5 \times 10^8
  • test6: N≤109\text{test6: } N \leq 10^9
  • test7: N≤109\text{test7: } N \leq 10^9
  • test8: N≤231−1\text{test8: } N \leq 2^{31}-1
  • test9: N≤231−1\text{test9: } N \leq 2^{31}-1
  • test10: N≤231−1\text{test10: } N \leq 2^{31}-1