​题目描述

就算是聪明的出题人也是从猩猩进化而来的。 一个物种拥有的基因可以简化地用两个数$(A, B)$表示 (是否太过简化了？)。每次进化，这个物种的基因会变为 $(A,A+B)$ 或者 $(A+B,B)$。 现在科学家已经知道了 $n$个物种的基因 $(a_1, b_1)$, ... , $(an, bn)$。他们新测出来了 $q$ 个物种的基因 $(c_1, d_1)$ , ... , $(cq, dq)$。
聪明的出题人想要知道，对于每个新测出来基因的物种，他们可能是多少种已知物种的祖先。 一个物种可能是另一个物种的祖先，当且仅当这个物种的基因可以经过若干次进化得到另一个物种的基因 (也可能0次进化) 。

输入格式

输入的第一行包含两个正整数 $n, q$，用空格隔开，表示已知的基因的物种数和新测的物种数。
接下来 $n$ 行，每行包含用空格隔开的两个整数 $a_i$ 和 $b_i$。
接下来 $q$ 行，每行包含用空格隔开的两个整数 $c_i$ 和 $d_i$。

输出格式

输出有 $q$ 行，每行包含一个正整数，即新测物种可能是多少种已知物种的祖先。

样例数据

3 4
6 9
5 3
1 1
6 3
1 2
2 1
5 3

1
0
1
1

2 2
7 14
7 14
7 7
7 14

2
2

数据范围

对于 $20\%$ 的数据有 $1 \leq n \leq 10, 1 \leq q \leq 10$
对于 $40\%$ 的数据有 $1 \leq n \leq 100, 1 \leq q \leq 100$
对于 $70\%$ 的数据有 $1 \leq n \leq 1000, 1 \leq q \leq 1000$
对于 $100\%$ 的数据有 $1 \leq n \leq 5 \times 10^4 , 1 \leq q \leq 5 \times 10^4, 1\leq a_i , b_i , c_i , d_i \leq 10^{18}$.