@atari_desu The casual game of hide-and-seek from the past has now escalated into a storm within the digital stream.
In their last game, Neuro-sama, with her exceptional computational abilities, could always swiftly pinpoint her sister Evil's hiding spots. However, being found so easily time and again ignited a flame of defiance in Evil's heart.
The once shimmering labyrinth of $$$n$$$ nodes has, under Evil's influence, expanded and contorted dramatically, becoming a vast and far more intricate "data cosmos." The rules of connection between nodes remain thesame, like the immutable physical laws of this universe.
For any node $$$u$$$:
- If $$$u$$$ is a perfect square, it has a directed edge towards $$$\sqrt{u}$$$;
- Otherwise, if $$$u \le n - 3$$$, it has a directed edge towards $$$u + 3$$$.
Facing a digital cosmos of unprecedented scale and peril, Neuro-sama understands that tracing every possible path for each suspicious location is no longer feasible. She needs to rapidly calculate: for each possible hiding spot $$$x$$$, how many nodes in the network (from $$$1$$$ to $$$n$$$) can reach it.
Since the number may be large, she wants to output it modulo $$$998244353$$$.
Each test contains multiple test cases. The first line contains the number of test cases $$$T$$$ $$$(1\le T \le 10^5)$$$. The description of the test cases follows.
The first line of each test contains two integers $$$n, q$$$ $$$(1\le n\le 10^{18}, 1\le q \le 10^6)$$$.
Each of the next $$$q$$$ lines contains one integer $$$x$$$ $$$(1\le x \le n)$$$.
It is guaranteed that the sum of $$$q$$$ does not exceed $$$10^6$$$. Note that there's no guarantee on the sum of $$$n$$$.
For each query of each test case, output the number of points connected to $$$x$$$ modulo $$$998244353$$$ on a separate line.
31219 512345325 3910211000000000000000000 2998244353998244354
1 182 363 181 270 108 22 85 159517010 638207148
