Chacha on Independence Day

0

0 votes
Medium, easy-medium, merge sort tree
Problem

Chacha wanted to do something different on this independence day, so as usual he decided to get high. While being high he gets emotional about positive numbers and their positive divisors.

Seeing his friend Genius around, he shoots Q queries towards him in the form of L,R and k, and Genius needs to answer the number of positive integers in the range [L, R], such that number of divisors of each of those integers is less than or equal to k.

The Genius is not feeling very genius today. Help him answer Chacha, as Chacha is his very good friend.

_______________________________________________________

Input format:

First line contains Q the number of queries Chacha shoots. Each of the next Q lines contain three positive integers, L,R and k.

Output format:

For each of the query print the required answer in new line.

Constraints:

1Q105

1LR105

1k106

Time Limit: 1
Memory Limit: 256
Source Limit:
Editor Image

?