B"In this sad world full of imperfections, ugly segment trees exist. A segment tree is a tree where each node represents a segment and has its number. A segment tree for an array of n elements can be built in a recursive manner. Let's say function operatorname{build}(v,l,r) builds the segment tree rooted in the node with number v and it corresponds to the segment [l,r] . Now let's define operatorname{build}(v,l,r) : So, the whole tree is built by calling operatorname{build}(1,1,n) . Now Ibti will construct a segment tree for an array with n elements. He wants to find the sum of operatorname{lca}^ dagger(S) , where S is a non-empty subset of leaves. Notice that there are exactly 2^n - 1 possible subsets. Since this sum can be very large, output it modulo 998 ,244 ,353 . ^ dagger operatorname{lca}(S) is the number of the least common ancestor for the nodes that are in S . Each test consists of multiple test cases. The first line contains a single integer t ( 1 <= t <= 10^3 ) -- the number of test cases. The description of the test cases follows. The first line of each test case contains a single integer n ( 2 <= n <= 10^{18} ) -- the length of the array for which the segment tree is built. For each test case, output a single integer -- the required sum modulo 998 ,244 ,353 . In the first test case: Let's look at all subsets of leaves. Thus, the answer is 2+3+1=6 . In the second test case: Let's look at all subsets of leaves. Thus, the answer is 4+5+3+2+1+1+1=17 . "...