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.)

Constraints

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

Input

Input is given from Standard Input in the following format:

$N$

Output

Print the answer.

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