熊猫先生喜欢数多边形。今天，他想计算满足以下条件的非同构凸多边形的数量：多边形有 $m$ 条边，每条边的长度均为正整数，周长恰好为 $n$，且没有两条边共线。

熊猫先生认为，这样的多边形可以用一个序列 $[l_1, l_2, \dots, l_m]$ 来描述，即其各边的长度（顺序不限）。一个多边形可能有多个描述序列。每个描述序列可以从多边形的任意一条边开始，按顺时针或逆时针方向遍历所有边，使得每条边恰好出现一次。

熊猫先生称两个凸多边形 $P$ 和 $Q$ 是同构的，当且仅当存在 $P$ 的一个描述序列 $A = [a_1, a_2, \dots, a_x]$ 和 $Q$ 的一个描述序列 $B = [b_1, b_2, \dots, b_y]$，使得 $x = y$ 且对于 $i = 1, 2, \dots, x$ 都有 $a_i = b_i$。

请你帮助熊猫先生计算这些多边形的数量。为了避免输出数据过大，你只需要输出答案对 $(10^9 + 7)$ 取模的结果。

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$ ($1 \le T \le 10^4$)，表示测试数据的组数。对于每组测试数据：

第一行包含两个整数 $n$ 和 $m$ ($3 \le m \le n \le 10^7$)。

输出格式

对于每组测试数据，输出不同多边形的数量对 $(10^9 + 7)$ 取模的结果，每组结果占一行。

样例

样例输入 1

4
3 3
4 3
5 3
7 4

样例输出 1

1
0
1
3

说明

对于第三个样例，只有一种类型的凸多边形，其描述序列可以是 $[1, 2, 2]$、$[2, 1, 2]$ 或 $[2, 2, 1]$。

对于最后一个样例，有三种类型的凸多边形，其描述序列分别为 $[1, 2, 2, 2]$、$[1, 1, 2, 3]$ 和 $[1, 2, 1, 3]$。

注意，描述序列为 $[1, 2, 1, 3]$ 的多边形与描述序列为 $[1, 3, 1, 2]$ 的多边形是同构的。