当前没有测试数据。

题目描述

Doctor Elephant is testing his new program: output the bitwise or of the numbers inputed. He has decided to input $n$ multiples of 3 and the output of the program should be his favorite number $a$. He wants to know how many possible sequences are there. Because the answer can be large, you only need to output the answer modulo $998244353$.

输入格式

There're multiple test cases in a test file. The first line contains a positive integer $T$ - the number of test cases. In each of the following $T$ lines there're two non-negative integers $n$ and $a$.

输出格式

For each test case output a line - the number of such sequences modulo $998244353$.

样例

样例输入 1

3
3 3
2 7
233 333

样例输出 1

7
2
650745136

数据范围与提示

1≤T≤500，1≤n≤10^18,0≤a≤10^18。