Problem Statement

You are given an integer N.
Find the number of pairs of integers (x, y) that satisfy the following conditions, modulo 998244353.

• $1 \leq x,y \leq N$.

• x^2-y is a square number. (Assume 0 is also a square number.)

Input

Input is given from Standard Input in the following format:
N

Output

Print the answer.

Constraints

• $1 \leq N \leq 10^{12}$
• All values in input are integers.

Sample Input 1

3

Sample Output 1

2

We have the following two pairs.

• x=1,y=1

• x=2,y=3

Sample Input 2

10

Sample Output 2

8

Sample Input 3

10000000000

Sample Output 3

52583544

见题面 Input 部分

见题面 Output 部分