SP16282 TAP2013H - Horace and his primes

霍勒斯喜欢在卧室的黑板上写自然数。他的一个常玩的游戏是这样的：首先，他写下一个数 $n$，然后写下所有能整除 $n$ 的不同质数的和，依次继续，直到黑板上的数变成质数为止。例如，如果霍勒斯从 $n = 90$ 开始，因为 $90 = 2 \times 3^2 \times 5$，下一个数将是 $2 + 3 + 5 = 10$；接着，$10 = 2 \times 5$，所以他写下 $2 + 5 = 7$；最后，$7$ 是质数，因此游戏结束。 具体来说，对每个不小于 2 的自然数 $n$，我们可以定义一个序列，该序列的第一个元素是 $n$，而之后的每个新元素是前一个元素的所有质因数的和。游戏的"阶数"指的是序列中第一个质数出现的位置，这也就是游戏结束时黑板上所有数字的个数。在之前的例子中，n = 90时，游戏的阶数为 $K = 3$，因为书写的数字依次为 $90$、$10$ 和 $7$。

第一行输入一个整数 $P$，表示霍勒斯想问的问题总数（$1 \leq P \leq 10^6$）。接下来的 $P$ 行中，每一行包含三个整数 $A$、$B$ 和 $K$，表示霍勒斯想知道有多少个不同的 $n$ 满足 $A \leq n \leq B$ 且游戏从 $n$ 开始的阶数为 $K$（$2 \leq A \leq B \leq 10^6$，$1 \leq K \leq 10^6$）。

输出共 $P$ 行，每行输出一个整数，按序回答霍勒斯提问的结果。 **本翻译由 AI 自动生成**