Counting Divisors

Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 524288/524288 K (Java/Others)

Problem Description

In mathematics, the function 

d(n) denotes the number of divisors of positive integer n.

For example, d(12)=6 because 1,2,3,4,6,12 are all 12's divisors.

In this problem, given l,r and k, your task is to calculate the following thing :

(∑i=lrd(ik))mod998244353

 

 

Input

The first line of the input contains an integer 

T(1≤T≤15), denoting the number of test cases.

In each test case, there are 3 integers l,r,k(1≤l≤r≤1012,r−l≤106,1≤k≤107).

 

 

Output

For each test case, print a single line containing an integer, denoting the answer.

 

 

Sample Input

3 1 5 1 1 10 2 1 100 3

 

 

Sample Output

10 48 2302

 

 

Source

官方题解：

　　唯一分解定理

#pragma comment(linker, "/STACK:1024000000,1024000000")#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include