SP20170 COLORSEG - Coloring Segments

进行有趣的活动本身并不坏，但如果在此过程中对他人不尊重，则无法接受。北南大学的某些学生做了这样的错误行为，因此作为惩罚，他们需要解决这个问题。而你作为他们的朋友，应该给予帮助。 你有 $N$ 个相连的线段，这些线段可以按顺序标号为 $1$ 到 $N$，如图所示： 现在，你需要为这些线段涂上颜色。可供使用的颜色被编号为 $1$ 到 $M$。你需要计算以下条件成立的涂色方法数： - 设 $U = \text{color}(i) + \text{color}(j)$ - 设 $V = \text{color}(j) + \text{color}(k)$ - 其中 $\gcd(U, V) = 1$ 条件中 $1 \le i < j < k \le N$ 且 $j = i + 1, k = j + 1$。这里的 $i, j, k$ 分别表示线段的索引，$\text{color}(i)$ 表示第 $i$ 条线段所使用的颜色。

输入以一个整数 $T$ 开始，表示测试用例的数量。接下来的每个测试用例包含两个整数 $N$ 和 $M$，分别代表线段的数量和可用颜色的数量。

对于每个测试用例，输出一个整数，表示满足条件的合法涂色方法数。由于方法数可能很大，结果请对 $10^9 + 7$ 取模。

- $1 \le T \le 100$ - $1 \le N \le 100$ - $1 \le M \le 100$ **本翻译由 AI 自动生成**