Số Chính Phương là là số tự nhiên có căn bậc hai là một số tự nhiên, hay nói cách khác, số chính phương bằng bình phương của một số nguyên không âm.

Ví dụ về các Số Chính Phương đầu tiên: \(0,1,4,9,16,...\)

Yêu Cầu: Cho một số nguyên dương \(N\). Hãy đếm số cặp \((x,y)\) thỏa mãn tất cả các điều kiện sau:

• \(1 \le x,y \le N\).
• \(x^2-y\) là số chính phương.

Vì kết quả có thể quá lớn, hãy in ra đáp án bài toán sau khi chia lấy dư cho \(998244353\).

Input

• Chứa một số nguyên dương \(N\) duy nhất \((1 \le N \le 10^{12})\).

Output

• In ra kết quả bài toán sau khi chia lấy dư cho \(998244353\).

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(1 \le N \le 5000\).
• Subtask \(2\) (\(30\%\) số điểm): \(5000 < N \le 10^6\).
• Subtask \(3\) (\(50\%\) số điểm): Không có ràng buộc gì thêm.

Example

3

2