Define F(n, k) = Sum of k^th powers of all divisors of n, so for example F(6, 2) = 1^2 + 2^2 + 3^2 + 6^2 = 50

Define further G(a, b, k) as: Sum of F(j, k) where j varies from a to b both inclusive.

Your task is to find G(a, b, k) given a, b and k.

As values of G can get very large, you only need to output the value of G(a, b, k) modulo 10^9+7.

Input

First line of input file contains a single integer T - denoting the number of test cases.

The follow description of T test cases. Each test case occupies exactly one line which contains three space separated integers a, b and k.

Output

Output your result for each test case in a new line.

Sample

Input:
2
2 2 1
1 3 2

Output:
3
16

Description of Sample

In case 1, we are to find sum of divisors of 2. which is nothing but 1 + 2 = 3.

In case 2, we are to find sum of squares of divisors of 1, 2 and 3. So for 1 sum is = 1. For 2 sum is = 1^2 + 2^2 = 5. For 3 sum is = 1^2 + 3^2=10. So answer is 16.

Constraints

1 <= a <= b <= 10^5

1 <= k <= 10^5

Number of test cases <= 20