問題文

整数 $N$ が与えられます． 以下の条件を満たす整数の組 $(x,y)$ の個数を $998244353$ で割った余りを求めてください．

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

• $x^2-y$ は平方数である．（特に，$0$ も平方数とする．）

制約

• $1 \\leq N \\leq 10^{12}$
• 入力される値はすべて整数である

入力

入力は以下の形式で標準入力から与えられる．

$N$

出力

答えを出力せよ．

入力例 1

3

出力例 1

2

以下の $2$ 通りが考えられます．

• $x=1,y=1$

• $x=2,y=3$

入力例 2

10

出力例 2

8

入力例 3

10000000000

出力例 3

52583544