AT_arc200_e [ARC200E] popcount <= 2

You are given positive integers $ N,M $ . Find the number, modulo $ 998244353 $ , of non-negative integer sequences $ A=(A_1,A_2,\ldots,A_N) $ of length $ N $ that satisfy all the following conditions. - $ 0\le A_i < 2^M $ $ (1\le i\le N) $ - $ \operatorname{popcount}(A_i\oplus A_j) \le 2 $ $ (1\le i < j\le N) $ Here, for non-negative integers $ x,y $ , we denote by $ x\oplus y $ the bitwise $ \mathrm{XOR} $ operation of $ x $ and $ y $ , and by $ \operatorname{popcount}(x) $ the popcount of $ x $ . You are given $ T $ test cases, so find the answer for each. What is bitwise $ \mathrm{XOR} $ operation? The bitwise $ \mathrm{XOR} $ of non-negative integers $ A, B $ , denoted $ A \oplus B $ , is defined as follows. - When $ A \oplus B $ is written in binary, the digit in the $ 2^k $ ( $ k \geq 0 $ ) place is $ 1 $ if exactly one of $ A, B $ has $ 1 $ in the $ 2^k $ place when written in binary, and $ 0 $ otherwise. For example, $ 3 \oplus 5 = 6 $ (in binary: $ 011 \oplus 101 = 110 $ ). What is popcount?For a non-negative integer $ x $ , $ \operatorname{popcount}(x) $ is the number of $ 1 $ s when $ x $ is written in binary. More precisely, for a non-negative integer $ x $ such that $ \displaystyle x=\sum _ {i=0} ^ \infty b _ i2 ^ i\ (b _ i\in\lbrace0,1\rbrace) $ , we have $ \displaystyle\operatorname{popcount}(x)=\sum _ {i=0} ^ \infty b _ i $ . For example, $ 13 $ in binary is `1101`, so we have $ \operatorname{popcount}(13)=3 $ .

The input is given from Standard Input in the following format: > $ T $ $ \text{case}_1 $ $ \text{case}_2 $ $ \vdots $ $ \text{case}_T $ Each test case is given in the following format: > $ N $ $ M $

Output $ T $ lines. The $ i $ -th line should contain the answer for the $ i $ -th test case.

### Sample Explanation 1 Consider the first test case. For example, $ A=(4,5) $ satisfies the conditions because each element is between $ 0 $ and $ 2^3-1=7 $ , and $ \operatorname{popcount}(4\oplus 5)=\operatorname{popcount}(1)=1\le 2 $ . On the other hand, neither $ A=(2,5) $ nor $ A=(0,7) $ satisfies the conditions. There are $ 56 $ sequences $ A $ that satisfy the conditions, so output $ 56 $ on the first line. ### Constraints - $ 1\le T\le 2\times 10^5 $ - $ 2\le N,M < 998244353 $ - All input values are integers.