5632：Rikka with Array

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.