Michael is teaching his recitation and he's trying to come up with two numbers ~a~ and ~b~ to use in a demonstration for his students. For the demonstration to work he know that ~a~ and ~b~ must be integers within the bounds ~0 \leq a \leq A~ and ~0 \leq b \leq B~ for given integers ~A~ and ~B~. However Michael also knows that his students have very specific tastes: they will only pay attention to his demonstration if the sum ~a+b~ is a square number (i.e. there exists a non-negative integer ~c~ such that ~a + b = c^2~).

Before Michael makes his choices for ~a~ and ~b~ he wants to know how many valid choices he has. As such, compute the number of valid pairs ~a, b~ with a square sum. As the answer may be large, compute this value modulo ~998244353~.

Michael will also be planning ahead for the next ~T~ recitations and will have one question for each recitation.

Constraints

~1 \leq T \leq 1000~

~1 \leq A, B \leq 10^{18}~

Subtask 1 [20%]

~T = 1~

~1 \leq A, B \leq 1000~

Subtask 2 [20%]

~T = 1~

~1 \leq A, B \leq 10^6~

Subtask 3 [40%]

~1 \leq T \leq 100~

~1 \leq A, B \leq 10^{10}~

Subtask 4 [20%]

No additional constraints.

Input Specification

The first line contains the integer ~T~.

The following ~T~ lines each contain two integers: ~A~ and ~B~ for each test case.

Output Specification

Output ~T~ lines.

On the ~i~th line output a single integer - the number of valid pairs with square sum for testcase ~i~, reduced modulo ~998244353~.

Sample Input

3
3 5
9982 44353
123456789 123456789

Sample Output

7
1551747
923038039

Note

The true answer for the third case of the sample is 757592257613 prior to the modulo operation.