在制作本题时，可能用到也可能没用到麦角酸二乙酰胺。

在本题中，函数被隐式地假定为以单个非负整数作为参数，并产生单个非负整数作为结果。

$f$ 是一个函数，$f(x) = 1 + 2 + \dots + x$。更正式地说，$f(x)$ 是所有小于或等于 $x$ 的正整数之和。

$s_k$ 是一个函数族。$s_0$ 是恒等函数（$s_0(x) = x$），且 $s_k(x) = s_{k-1}(f(x) + k)$。

给定 $t$ 组测试用例。第 $i$ 组测试用例包含三个整数 $x_i, k_i$ 和 $p_i$。对于每个测试用例，请找到一个整数 $m_i$，使得 $-1 \le m_i \le p_i - 1$ 且 $s_{k_i}(x_i) \pmod{p_i} \not\equiv m_i$。你使用 $m_i = -1$ 的次数不得超过 $20$ 次。保证所有的 $p_i$ 两两不同。注意，$a \pmod p \ge 0$，其中 $a$ 为任意整数，因此对于任何特定的测试用例，$m_i = -1$ 都是正确的。

为什么要这样做？很简单。寻找正确答案既容易又随大流。另一方面，寻找错误答案既具有挑战性又独具匠心。然而，在本题中，由于 $p = 1$ 的情况，这变得有点太难了。所以你决定跳过一些测试用例，使用 $m_i = -1$ 作为通配符。听起来很合理（才怪）。

输入格式

第一行包含一个整数 $t$ ($1 \le t \le 5000$)，表示测试用例的数量。 接下来 $t$ 行，第 $i$ 行包含三个整数 $x_i, k_i, p_i$ ($1 \le x_i \le 10^9, 0 \le k_i \le 10^5, 1 \le p_i \le 10^4$)。 保证 $\forall i \neq j, p_i \neq p_j$。

输出格式

输出 $t$ 个整数。第 $i$ 个整数应等于 $m_i$。 满足 $m_i = -1$ 的索引 $i$ 的数量不得超过 $20$。

样例

样例输入 1

3
4 0 1
2 2 2
4 1 3

样例输出 1

-1
1
0

样例输入 2

2
1 3 2
6 0 3

样例输出 2

-1
1

样例输入 3

2
1 3 2
2 2 3

样例输出 3

0
2