Problem Description

As we know, Rikka is poor at math. Yuta is worrying about this situation, so he gives Rikka some math tasks to practice. There is one of them:

Yuta has an array $A$ of length $n$，and the $i$th element of $A$ is equal to the sum of all digits of $i$ in binary representation. For example,$A[1]=1, A[3]=2, A[10]=2$.

Now, Yuta wants to know the number of the pairs $(i,j)(1 \leq i < j \leq n)$ which satisfy $A[i] > A[j]$.

It is too difficult for Rikka. Can you help her?

Input

The first line contains a number $T(T \leq 10)$——The number of the testcases.

For each testcase, the first line contains a number $n(n \leq 10^{300})$.

Output

For each testcase, print a single number. The answer may be very large, so you only need to print the answer modulo 998244353.

1
10

7

When $n=10$, $A$ is equal to $1,1,2,1,2,2,3,1,2,2$.

So the answer is $7$.