F.A.Q
Hand In Hand
Online Acmers
Problem Archive
Realtime Judge Status
Authors Ranklist
 
     C/C++/Java Exams     
ACM Steps
Go to Job
Contest LiveCast
ICPC@China
Best Coder beta
VIP | STD Contests
    DIY | Web-DIY beta
Author ID 
Password 
 Register new ID

Rikka with Equation

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 512000/512000 K (Java/Others)
Total Submission(s): 48    Accepted Submission(s): 0


Problem Description
The conclusion of Hilbert's tenth problem shows that it's impossible to design an algorithm to calculate the integral solutions of an arbitrary equation. But for some simple equation, we can easily check it.

For example, to check if there exist two integers $x,y$ which satisfy $x^2 + y^2 = a$ and $xy =b$: We can calculate $x+y = \pm \sqrt{a+2b},x-y=\pm\sqrt{a-2b}$ and then check if both $x$ and $y$ could be integers.

Rikka thinks this task is too simple and she wants to make it look harder. Rikka knows, sometimes if you consider the equality after modulo $m$, the task will be different. So, she wants to do the same thing to this problem.

She call a tuple $(a,b,m)(0 \leq a,b < m)$ valid if and only if there exist two integers $x$ and $y$ which satisfy $x^2+y^2\equiv a \mod m, xy\equiv b \mod m$. After showing you a positive integer $n$, she wants you to calculate the number of valid tuples $(a,b,m)$ with $m \leq n$.

 

Input
The first line contains a single integer $t(1 \leq t \leq 10^5)$, the numebr of the testcases.

For each testcase, the first line contains a single number $n(1 \leq n \leq 10^7)$.
 

Output
For each testcase, output a single line with a single integer, the answer modulo $998244353$.
 

Sample Input
5 3 5 10 100 1000
 

Sample Output
8 22 104 45933 32791150
 

Source
 

Statistic | Submit | Discuss | Note
Hangzhou Dianzi University Online Judge 3.0
Copyright © 2005-2024 HDU ACM Team. All Rights Reserved.
Designer & Developer : Wang Rongtao LinLe GaoJie GanLu
Total 0.000000(s) query 1, Server time : 2024-11-25 14:57:39, Gzip enabled