Nayra doesn’t like stories of people receiving random numbers as birthday presents, but this time she received three numbers (L, R and B) as a present for her own birthday! After struggling for a day trying to figure out what to do with these numbers, she asked Aryan for help. He asked her to find sum of XOR of digits of numbers between L and R (both inclusive) when written in Base B.

Formally, Given L and R find sum of xor of digits of X ∈ [L, R] when X is written in base B.
Since, the sum is very large print it modulo 998244353.

Input

• The first line of input contains a single integer T denoting the number of test cases. The description of T test cases follows.
• The first and only line of each test case contains three space-separated integers L, R and B

Output

For each test, print one line containing the sum of digital root of such X

Constraints

• 1 ≤ T ≤ 10^5
• 1 ≤ L ≤ R ≤ 10^18
• 2 ≤ B ≤ 64
• Sum of B*B over all test cases ≤ 10^6

Subtasks

• Subtask #1 (20 points): 1 ≤ L ≤ R ≤ 100, 2 ≤ B ≤ 16
• Subtask #2 (80 points): Original constraints.

Sample 1

Input

3
3 10 2
9 11 3
12 18 4

Output

3
4
10