如果一个整数 $N$ 可以表示为 $N$ 的 $K$ 个约数（不一定不同）之和，则称其为 $K$-可表示的。求在 $A$ 到 $B$（含）之间有多少个 $K$-可表示的整数。
输入格式
第一行包含一个整数 $T$ ($1 \le T \le 5 \cdot 10^4$) —— 测试用例的数量。
接下来的 $T$ 行包含测试用例的描述。每行包含三个由空格隔开的整数 $A, B, K$ ($1 \le A \le B \le 10^{18}, 2 \le K \le 7$)。
输出格式
输出 $T$ 行，包含对应测试用例的答案。
样例
输入样例 1
3 1 5 3 5 10 2 4 6 4
输出样例 1
2 3 2
说明
在第一个测试用例中，数字 3 和 4 是 3-可表示的：$3 = 1 + 1 + 1$，$4 = 1 + 1 + 2$。
在第三个测试用例中，数字 4 和 6 是 4-可表示的：$4 = 1 + 1 + 1 + 1$，$6 = 1 + 1 + 1 + 3$。