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.