题目描述

丽丽正在数数，她喜欢一个数字，当且仅当这个数字能够被拆分成恰好 $k$ 个互不相同的质数的乘积。现在，她想要知道在区间 $[l, r]$ 中有多少个她喜欢的数字。但由于丽丽是个数学笨蛋，这个问题就交给你啦！丽丽会询问你 $q$ 次，每次都会给出 $k, l, r$。

输入格式

数据第一行为一个正整数 $q$，表示丽丽的询问次数。

接下来 $q$ 行，每行三个正整数 $k, l, r$，含义见题目描述。

输出格式

输出共 $q$ 行，其中第 $i$ 行包括一个整数，表示第 $i$ 次询问的答案。

样例数据

6
2 8 10
2 6 8
2 4 10
1 5 7
1 8 9
2 1 9

1
1
2
2
0
1

大样例

P151001.in/P151001.out

P151002.in/P151002.out

P151003.in/P151003.out

P151004.in/P151004.out

P151005.in/P151005.out

数据范围

对于 $20\%$ 的数据，$1 \leq q \leq 10^3, 1 \leq k \leq 4, 1 \leq l \leq r \leq 10^3$

对于 $50\%$ 的数据，$1 \leq q \leq 10^6, 1 \leq k \leq 6, 1 \leq l \leq r \leq 10^6$

对于 $100\%$ 的数据，$1 \leq q \leq 10^6, 1 \leq k \leq 8, 1 \leq l \leq r \leq 10^7$