Alice 在上研究生拓扑课时了解到，存在一种拓扑学证明可以说明素数有无穷多个。

当然，拓扑学是对拓扑结构的研究。

拓扑可以定义为一组在集合并集和交集运算下表现良好的集合——这些集合被称为开集。为了使拓扑证明有效，我们需要在整数上定义一种拓扑，称为等距整数拓扑。

总之，Alice 没跟上进度，完全听不懂这些，于是她决定忽略这一切，在笔记本上涂鸦一些完全无关的内容。

令 $U_n = \{1, 2, 3, \dots, n\}$。如果一个子集 $S \subseteq U_n$ 满足以下条件，则称其为素数间隔的（prime-spaced）： * 对于所有不同的 $a, b \in S$，都有 $|a - b|$ 是素数。

一个整数 $n$ 是素数，当且仅当 $n > 1$ 且 $n$ 除了 1 和它本身外没有其他正约数。

例如，假设取 $n = 6$，则 $U_n = \{1, 2, 3, 4, 5, 6\}$。 空集是（空洞地）素数间隔的。 $\{1\}$ 是（空洞地）素数间隔的。 $\{1, 6\}$ 是素数间隔的，因为 $|1 - 6| = 5$，它是素数。 $\{1, 5\}$ 不是素数间隔的，因为 $|1 - 5| = 4$，它不是素数。 $\{1, 3, 6\}$ 是素数间隔的，因为 $|1 - 3|$、$|1 - 6|$ 和 $|3 - 6|$ 均为素数。 $\{1, 2, 4\}$ 不是素数间隔的，因为 $|1 - 2| = 1$，它不是素数。

给定正整数 $n$ 和 $k$，求 $U_n$ 中大小为 $k$ 的素数间隔子集有多少个（模 104206969）。每个文件中包含 $T$ 个独立的测试用例。

输入格式

输入的第一行包含一个整数 $T$，表示测试用例的数量。接下来是 $T$ 个测试用例的描述。

每个测试用例由一行组成，包含两个空格分隔的整数 $n$ 和 $k$。

输出格式

对于每个测试用例，输出一行，包含该测试用例的答案。

数据范围

$1 \le T \le 2 \times 10^5$ $1 \le k \le n \le 10^7$

样例

样例输入 1

3
5 2
6 3
10000000 10000000

样例输出 1

5
2
0

说明

一个完全没用的事实

令 $X$ 为 $U_n$ 的素数间隔子集的任意（可能为空的）集合。那么，$\bigcap_i X_i$ 也保证是 $U_n$ 的一个素数间隔子集。

上述事实与本题无关，也与拓扑学无关。它完全没用。