给定 $n$ 个贵族代码对 $(a_1, b_1), (a_2, b_2), \dots, (a_n, b_n)$ 和 $q$ 次询问。在每次询问中，给定一个数对 $(A, B)$，你需要计算有多少个贵族代码对可以由给定的数对 $(A, B)$ 变换得到。每次变换可以将当前的数对 $(A, B)$ 变为 $(A + B, B)$ 或 $(A, A + B)$。你可以进行任意次数的变换操作（也可以不进行任何操作）。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 100$)，表示测试用例的数量。对于每个测试用例：

第一行包含两个整数 $n$ 和 $q$ ($1 \le n, q \le 50\,000$)，分别表示贵族代码对的数量和询问的数量。

接下来的 $n$ 行中，第 $i$ 行包含两个整数 $a_i$ 和 $b_i$ ($1 \le a_i, b_i \le 10^{18}$)，描述第 $i$ 个贵族代码对。

接下来的 $q$ 行中，第 $i$ 行包含两个整数 $A$ 和 $B$ ($1 \le A, B \le 10^{18}$)，描述第 $i$ 次询问中的数对。

保证所有测试用例中 $n$ 的总和不超过 $500\,000$，且所有 $q$ 的总和不超过 $500\,000$。

输出格式

对于每次询问，输出一行，包含一个整数，表示可以由给定数对变换得到的贵族代码对的数量。注意，两个贵族代码对 $(a_i, b_i)$ 和 $(a_j, b_j)$ 被视为不同，当且仅当 $i \neq j$。

样例

输入 1

2
3 4
6 9
5 3
1 1
6 3
1 2
2 1
5 3
2 2
7 14
7 14
7 7
7 14

输出 1

1
0
1
1
2
2