题目描述

给定一个整数 $N$。请计算满足以下条件的整数对 $(x, y)$ 的个数，并将结果对 $998244353$ 取模。

• $1 \leq x, y \leq N$。
• $x^2 - y$ 是一个平方数（特别地，$0$ 也视为平方数）。

输入格式

输入为标准输入，格式如下：

$N$

输出格式

请输出答案。

样例 1

输入

3

输出

2

样例 2

输入

10

输出

8

样例 3

输入

10000000000

输出

52583544

说明/提示

限制条件

• $1 \leq N \leq 10^{12}$
• 输入的值均为整数。

样例解释 1

有以下 $2$ 种情况满足条件：

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

由 ChatGPT 4.1 翻译