题目描述

千秋不喜欢现有的质数定义。

现有的质数定义： 如果一个整数 $x \ge 2$，有且只有 $1$ 和 $x$ 两个因数，那么 $x$ 为质数，否则 $x$ 为合数。

千秋认为这样的质数定义过于严苛，大幅减少了质数的数量。千秋认为，如果 $x$ 满足下面条件中的任意一条，就应该被认为是千秋质数：

• $x$ 符合现有质数的定义；
• $x$ 的互不相同的质因数 $p_1, p_2, \dots, p_k$ 中，至少存在 $w$ 个质因数 $p_i$，满足 $p_i$ 中至少有一个数位（例如个位、十位或百位等）的数字为 $z$。

例如，当 $w=2, z=2$ 时，数字 $46$ 的质因数有 $2$ 和 $23$，这两个质因数都包含数字 $2$，因此 $46$ 符合千秋质数的定义。

千秋共有 $Q$ 个询问。他想知道在确定的 $w, z$ 之下，闭区间 $[L, R]$ 范围内共有多少个千秋质数。

输入格式

第一行包含三个整数 $w, z, Q$ —— 分别表示定义的阈值、指定的数位数字以及询问的次数。

接下来 $Q$ 行，每行包含两个正整数 $L, R$ —— 表示一组询问的区间范围。

输出格式

输出共 $Q$ 行，每行包含一个非负整数，表示对应询问的答案。

样例输入 1

2 2 3
1 10
46 46
20 50

样例输出 1

4
1
8

样例输入 2

1 0 3
1 100
100 202
202 202

样例输出 2

25
22
1

样例输入 3

3 3 3
1 40
30 300
333 1000

样例输出 3

12
52
102

说明

数据范围

设 $R_{\max}$ 为所有询问中出现的最大的 $R$ 值。

• 对于 $30\%$ 的测试点，保证 $1 \le Q \le 10$，$1 \le L \le R \le 10^3$；
• 对于另外 $30\%$ 的测试点，保证 $Q = 1$；
• 对于 $100\%$ 的测试点，保证 $1 \le Q \le 10^6$，$1 \le L \le R \le 5 \times 10^6$；
• 对于 $100\%$ 的测试点，保证 $1 \le w \le R_{\max}$，$0 \le z \le 9$。
• 保证所有的输入数值均为整数。