某天， chenbs 在写位运算时写出了如下 C++ 代码：
(11l<<i)
出题人非常害怕自己也这样写错，于是出了一道位运算题：
给定 n,x,y,z，让你构造 n 个数 $ai\ (1\le i\le n)，使得 \mathop{\operatorname{and}}\limits{i=1}^n ai=x,\mathop{\operatorname{or}}\limits{i=1}^n ai=y,\mathop{\operatorname{xor}}\limits{i=1}^n ai=z 且 \prod\limits{i=1}^na_i 最大。其中 \operatorname{and},\operatorname{or},\operatorname{xor}$ 表示位运算中的与、或、异或。
如果存在这样的 $ai，你需要求出 \max\prod\limits{i=1}^na_i 对 998244\red{8}53 取模的值；否则请输出 -1$。
本题有多组测试用例。
第一行输入一个正整数 T，表示测试用例组数。
接下来 T 行，每行输入四个非负整数 n,x,y,z。
共 T 行，对于每组数据：
如果无解，输出 -1；
否则输出一个非负整数，表示 \max\prod\limits_{i=1}^na_i 对 998244\red{8}53 取模的值。
2 3 2 7 6 8 6 55 36
54 -1
4 9 2 7 6 18 3 5 0 4 1 59 24 841039 0 7 7
6353046 -1 1464561 906098946
对于第一个样例的第一组数据，选择数字 3,3,6，因为 3\operatorname{and}3\operatorname{and}6=2,3\operatorname{or}3\operatorname{or}6=7,3\operatorname{xor}3\operatorname{xor}6=6 所以符合条件，可以证明乘积 54 最大。
对于第一个样例的第二组数据，不存在符合条件的序列 a。
| 测试点 | n \le | x,y,z < | T \le |
|---|---|---|---|
| 1 | 2 | 2^{30} | 10^4 |
| 2 | 4 | 2^4 | 100 |
| 3, 4 | 50 | ^ | ^ |
| 5, 6 | ^ | 2^6 | ^ |
| 7, 8 | 10^2 | 2^{30} | ^ |
| 9, 10 | 10^4 | ^ | ^ |
| 11, 12 | 10^{18} | 2^{60} | 10^2 |
| 13 \sim 15 | ^ | ^ | 10^3 |
| 16 \sim 20 | ^ | ^ | 10^4 |
对于所有数据，1\le n \le 10^{18}，0\le x,y,z < 2^{60}，1\le T \le 10^4。
洛谷月赛