Let us define the functions
and
as
Let
us define the functions
and
as
Here
divisors of n include both 1 and n. For example divisors of 6 are
1, 2, 3 and 6. So
and
Now
let us define two more function
and
as
Where
and
.
For
example,
and
.
Given a,b,k you have to calculate g(a,b,k) and h(a,b,k).
The first line of the input file contains an integer T (T ≤ 75) which denotes the total number of test cases.
The description of each test case is given below:
Three integers in a line. First integer is contains a, second integer is b and third integer is k. You may assume 0 < a ≤ b ≤ 1012, 0 < k < 2000.
For each test case print one line containing g(a,b,k) and h(a,b,k) separated by a space as defined above. As output may be very large print the output modulo 264.
2
5 12 3
1 100 3
13 53
217 3323