众所周知，萌萌哒六花不擅长数学，所以勇太给了她一些数学问题做练习，其中有一道是这样的： 有一个长度为 $n$ 的数组 $A$（下标为 $1$ 到 $n$），$A_i$ 为 $i$ 的二进制表示中的1的个数，例如 $A[1]=1, A[3]=2, A[10]=2$。 现在勇太想知道数组 $A$ 中满足 $A[i]>A[j]$ 的数对 $(i,j)(1 \leq i < j \leq n)$ 的个数。 当然，这个问题对于萌萌哒六花来说实在是太难了，你可以帮帮她吗？
第一行一个整数表示数据组数 $T(T \leq 10)$。
每组数据第一行一个整数表示 $n(n \leq 10^{300})$
对于每组数据输出一行一个整数表示答案，因为答案可能很大，你只需要输出答案对 $998244353$ 取模之后的结果。
1 10
7
当 $n=10$ 的时候，数组 $A$ 为 $1,1,2,1,2,2,3,1,2,2$。 答案为7。