Extra
Time
Divisor Time:2s Memory:256M AC:0% Submit:3

陈老师是个热爱数论的少女。    
她称n为k-可表达的当且仅当这个数n能被表示n的k个因子之和,注意这些因子可以相同。
她想求在A和B之间有多少k-可表达数,A和B之间包括A和B。
Input
第一行一个整数T表示数据总数。 接下来T行每行三个正整数A, B, K。
Output
一共T行,对于每个询问输出答案。
Constraints
对于10%的数据,有T ≤ 5, K ≤ 2, A, B ≤ 10^6
对于30%的数据,有T ≤ 50, K ≤ 4, A, B ≤ 10^6
对于50%的数据,有T ≤ 500, K ≤ 5, A, B ≤ 10^9
对于70%的数据,有T ≤ 5000, K ≤ 6, A, B ≤ 10^{12}
对于100%的数据,有T ≤ t \times 10^4, 2 ≤ K ≤ 7, 1 ≤ A ≤ B ≤ 10^{18}
Example

divisor.in divisor.out
3
1 5 3
5 10 2
4 6 4
2
3
2