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.
Sample Input
1
10
Sample Output
7
When $n=10$, $A$ is equal to $1,1,2,1,2,2,3,1,2,2$.
So the answer is $7$.
