题目描述

小王需要从 1 到 n 依次数数。

对于其中的每一个数 x，只有当它同时满足下面两个条件时，小王才会报出这个数：

1. x 恰好有 k 个不同的质因数；
2. x 的各位数字之和是一个质数。

例如，假设 k = 2：

• 12 = 2 × 2 × 3，有两个不同的质因数 2 和 3；它的各位数字之和为 1 + 2 = 3，是质数，所以小王会报出 12。
• 22 = 2 × 11，有两个不同的质因数，但它的各位数字之和为 2 + 2 = 4，不是质数，所以小王不会报出 22。
• 30 = 2 × 3 × 5，有三个不同的质因数，不满足第一个条件，所以小王不会报出 30。

现在给出 q 次询问，每次询问两个整数 l、r。

请你计算：在区间 [l, r] 内，小王一共会报出多少个数？

输入格式

第一行包含三个整数 n、k、q。

接下来 q 行，每行包含两个整数 l、r，表示一次询问的范围。

输出格式

输出 q 行，每行一个整数，表示对应区间内小王会报出的数的数量。

如果区间内没有符合条件的数，输出 0。

样例 1

输入：

30 2 5
1 10
1 20
11 25
24 30
1 30

输出：

0
3
4
0
4

样例 2

输入：

20 1 4
1 20
4 10
1 1
12 20

输出：

6
2
0
1

数据范围

对于所有测试数据：

• 1 ≤ n ≤ 10^6；
• 1 ≤ k ≤ 7；
• 1 ≤ q ≤ 10^5；
• 1 ≤ l ≤ r ≤ n。

注意：1 不是质数，也没有质因数。