题目描述

对于一个长度为 $n$ 的非负整数序列，定义该序列的权值为其 $2^n$ 个子序列的异或和之和。

例如，序列 $\{1,1\}$ 的权值为

$$0+(1)+(1)+(1\oplus 1)=2,$$

序列 $\{1,2\}$ 的权值为

$$0+1+2+(1\oplus 2)=6.$$

给定整数 $n,m,x$，请计算最小的非负整数 $k$，使得存在一个长度为 $n$ 且权值为 $k$ 的非负整数序列，并且满足

$$k\bmod m=x.$$

如果这样的 $k$ 不存在，则输出 $-1$。

这样的 $k$ 可能很大，输出时要求对 $998244353$ 取模。

注意，输出的结果是最小的 $k$ 取模后的结果，而不是“$k$ 取模后的最小结果”。

时间限制：2 秒。
空间限制：512 MiB。

输入格式

本题开启多组测试。

输入的第一行包含一个整数 $T$，表示测试数据组数。

对于每组测试数据，输入一行三个整数 $n,x,m$，表示一组询问。

输出格式

对于每组询问，输出一行一个整数表示答案。如果 $k$ 存在，则输出其可能的最小值对 $998244353$ 取模后的结果；否则输出 $-1$。

样例

输入

3
3 5 13
2 2 7
4 3 17

输出

28
6
-1

数据范围

对于 $100\%$ 的数据，保证

$$0\le T\le 100,\quad 1\le n\le 10^{10^4},\quad 0\le x<m\le 10^9.$$

保证奇数编号的测试点有 $x\ne 0$。

测试点编号	$n\le$	$m\le$	特殊性质
$1\sim 2$	5		无
$3\sim 4$	$10^8$	$10^5$
$5\sim 7$	$10^{18}$	$10^9$	A
$8\sim 10$	$10^{10^4}$		无

特殊性质 A：保证 $m$ 是质数。