题目描述

给定一个整数 $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

我们有以下两个整数对。

• $x=1,y=1$

• $x=2,y=3$

示例输入 2

10

示例输出 2

8

示例输入 3

10000000000

示例输出 3

52583544