Gauri 是韩国流行音乐组合 TWICE 的忠实粉丝。最近，TWICE 发布了一首名为“Talk That Talk”的歌曲，从那以后，Gauri 就被等距三元组深深吸引了。

给定一个整数 $t$ 和一个二进制字符串 $s$（其下标从 $1$ 到 $|s|$），我们将其 $t$-值定义为 TTT-三元组的数量。当且仅当满足以下条件时，三元组 $(i, j, k)$ 是一个 TTT-三元组：

1. $1 \le i < j < k \le |s|$
2. $j - i = k - j$，且 $1 \le j - i \le t$
3. $s_i = s_j = s_k$

今天，Gauri 收到了一份礼物，包含一个整数 $t$ 和一个长度为 $p - 1$ 的字符串 $w$，其中 $p$ 是一个素数。她注意到，对于所有 $1 \le x \le p - 1$，如果存在整数 $z$ 使得 $z^2 \equiv x \pmod p$，则 $w_x = 1$，否则 $w_x = 0$。请帮助 Gauri 计算 $w$ 的 $t$-值。

每个测试包含多个测试用例。共有 $T$ 个测试用例。

输入格式

第一行包含一个整数 $T$，表示测试用例的数量。 接下来的 $T$ 行，每行包含两个整数 $p$ 和 $t$。

数据范围

• $5 \le p \le 10^{12}$，且 $p$ 是一个素数。
• $1 \le t \le 10^6$
• $1 \le T \le 5 \cdot 10^5$
• 所有测试中 $t$ 的总和不超过 $10^6$。

输出格式

输出 $T$ 行，每行一个整数，表示对应测试用例中 $w$ 的 $t$-值。

样例

样例输入 1

7
7 32
13 1
13 2
67 11
2003 44
1000003 1984
999999999989 987654

样例输出 1

0
2
2
146
21510
495014784
246913256130162788

说明

当 $p = 13$ 时，我们得到 $w = 101100001101$，可能的 TTT-三元组为 $(5, 6, 7), (6, 7, 8), (2, 5, 8)$ 和 $(5, 8, 11)$。 现在如果 $t = 2$，后两个三元组满足 $j - i > t$，违反了条件 2。因此，对于 $p = 13, t = 2$，答案为 $2$。