该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

在繁忙的数字王国里，有一个小镇，镇上有许多数字住民。某天，镇长大人给数字们布置了一项任务：他想要知道，在给定的某个数字区间内，有多少个数字的因数个数恰好等于一个指定的数字 $k$。镇长希望这项任务能够迅速完成，因为他准备了丰厚的奖励。

这时候，你作为镇上的“数字探险家”，接到了这个任务。你需要在规定的时间内，计算出区间 $[l, r]$ 内有多少个数字，其因数个数正好为 $k$。一个整数的因数是任何能整除它的数字，包括$1$和它自身。

问题描述

给定一个整数区间 $[l, r]$，以及一个整数 $k$，你需要求出区间内因数个数为 $k$ 的数字个数。

输入格式

• 第一行输入2个整数 $T, s$，其中$T$表示测试点的数量。$s$可能是$0$或$1$，$s=1$表示以下$T$组测试数据中$k$的值保证全部相等，$s=0$则表示无此保证。

• 对于每个测试点，输入三个整数 $l, r, k$ $(1 ≤ l \leq r \leq 10^5 , 1 ≤ k \leq 20 )$，表示区间 $[l, r]$ 和目标因数个数 $k$。

输出格式

• 对于每个测试点，输出一个整数，表示区间 $[l, r]$ 内因数个数为 $k$ 的数字个数。

样例

样例输入1

5 0
1 10 1
1 10 2
1 10 3
1 10 4
1 10 5

样例输出1

1
4
2
3
0

解释：1-10中，每个数的因数个数分别是 1, 2, 2, 3, 2, 4, 2, 4, 3, 4, 其中有1个1，4个2，2个3，3个4，0个5.

数据范围

本题一共20组测试数据，数据范围分别如下：