Charm of Falling Flowers

In the beautiful Light Flower Forest, there are trees numbered from (l) to (r). For each tree with index (i), there exist (i-1) copies. Moreover, every tree is adorned with (n) light flowers numbered from (1) to (n). When the (j)-th flower on the (i)-th tree falls, it produces a charm value of (\lceil \log_{i}j\rceil) (note that (\lceil x\rceil) denotes the ceiling function).

When dusk falls, all flowers on all trees drop, and the total charm is defined as [ S = \sum_{i=l}^{r} (i-1) \sum_{j=1}^{n} \lceil \log_{i}j\rceil \bmod 998244353. ]

You are given (T) queries. Each query provides three integers (l), (r), and (n). For each query, compute (S) modulo (998244353).

inputFormat

The first line contains an integer (T) denoting the number of queries. Each of the following (T) lines contains three space-separated integers (l), (r), and (n).

outputFormat

For each query, output a single line containing the total charm value modulo (998244353).

sample

3
2 4 10
2 2 5
3 5 20

104
8
347