令 $a_n$ 是由以下递推公式定义的序列：
$$a_{n+2} = k \cdot a_{n+1} + a_n$$ $$a_0 = 0$$ $$a_1 = 1$$
给定一个特定的 $k \in \{1, 3, 5, 7\}$ 和一个奇素数 $p$，你的任务是求出 $a_p \bmod p$ 的值。
第一行给出一个整数 $Z \le 10^6$，表示接下来各行中描述的测试用例数量。
对于每个测试用例，第一行也是唯一的一行输入包含两个自然数 $p$ 和 $k$，其中 $p$ 是一个奇素数。
$k \in \{1, 3, 5, 7\}$。所有测试用例中数字 $p$ 的总长度（总位数）不超过 $10^6$。
对于每个测试用例，你应该恰好输出一行，包含 $a_p \bmod p$ 的值。
3 3 5 11 1 13 3
2 1 0
The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.
This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.
If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.
Guidelines: