题目描述

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

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

输入格式

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

$N$

输出格式

答えを出力せよ．

题目大意

现在给你一个数 $N$，求出满足下列条件的点对 $(x,y)$ 的个数对 998244353 取模后的值。

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

• $x^2-y$ 是一个完全平方数。特别的，0 也算一个完全平方数。

输入一个数，表示 $N$。

输出一个数，表示满足条件的点对的个数对 998244353 取模后的值。

3

2

10

8

10000000000

52583544

提示

制約

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

Sample Explanation 1

以下の $2$ 通りが考えられます． - $x=1,y=1$ - $x=2,y=3$