Score : $500$ points

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.

3

2

We have the following two pairs.

• $x=1,y=1$
• $x=2,y=3$

10

8

10000000000

52583544