7048: Xor
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：17
解决：16
题目描述
给定 $n$，求满足 $0 \le a , b \le n$ 且 $a + b = a \oplus b$ 的 $(a , b)$ 的个数。
保证存在一个正整数 $k$，使得 $n = 2 ^ {k} - 1$。
答案对 $998224353$ 取模。
注意：若 $a \not= b$，则我们认为 $(a , b)$ 和 $(b , a)$ 是不同的。
保证存在一个正整数 $k$，使得 $n = 2 ^ {k} - 1$。
答案对 $998224353$ 取模。
注意：若 $a \not= b$，则我们认为 $(a , b)$ 和 $(b , a)$ 是不同的。
输入
第一行一个正整数 $T$，表示数据组数。
接下来 $T$ 行，每行一个正整数 $k$，表示该组询问的 $n = 2 ^ {k} - 1$。($k≤10^{18}$)
接下来 $T$ 行，每行一个正整数 $k$，表示该组询问的 $n = 2 ^ {k} - 1$。($k≤10^{18}$)
输出
共 $T$ 行，每行一个正整数
样例输入 复制
3
1
20
114514样例输出 复制
3
492111342
211796379提示
$k = 1$ 时 $n = 1$。此时有 $(0 , 0) , (0 , 1) , (1 , 0)$ 三组合法的 $(a , b)$。