Define F(n, k) = Sum of k^th powers of all divisors of n, so for example F(6, 2) = 1² + 2² + 3² + 6² = 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⁹+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² = 5. For 3 sum is = 1² + 3² = 10. So answer is 16.

Constraints

1 ≤ a ≤ b ≤ 10⁵

1 ≤ k ≤ 10⁵

Number of test cases ≤ 20