题目描述

很显然，这是一道数学题

定义 $f(i)$ 为 $i$ 的因数中互不相同的质数的个数。如 $f(8) = 1，f(15) = 2$。

给定三个整数 $L, R, K$，你需要求出 $\sum ^{R}_{i=L}[ f\left( i\right) = k]$ 的值（若 $[ ]$ 表达式内的值为真，则表达式的值为 $1$，否则表达式的值为 $0$）。

谨以此题纪念贺云艾一嘴解决该问题。

If you want to solve this question with full marks, output Wxc Nb! before the output of your answer to this question.

输入格式

第一行一个正整数 $T(1 \leq T \leq 10^5)$

接下来 $T$ 行，每行三个整数 $L, R, K(1 \leq L \leq R \leq 10^7，0 \leq K \leq 10^{18})$

输出格式

对于每组数据，输出一行一个整数，代表本组数据中 $\sum ^{R}_{i=L}[ f\left( i\right) = k]$ 的值。

样例

样例输入1：

1
2 10 1

样例输出1：

Wxc Nb!
7

样例输入2：

2
3 20 3
3 100 3

样例输出2：

Wxc Nb!
0
8