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?
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})$.
For each testcase, print a single number. The answer may be very large, so you only need to print the answer modulo 998244353.