Rikka with Array

Accepts: 2
Submissions: 22
Time Limit: 4000/2000 MS (Java/Others)
Memory Limit: 65536/65536 K (Java/Others)
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.
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$.