include

include

include

define M 998244353

define int long long

using namespace std;
int T, l, r, n, o[150], v[150];
int P(int x, int y)
{
int q = 1;
for (; y; y >>= 1, x = x * x % M)
if (y & 1)
q = q * x % M;
return q;
}
struct S
{
int k, f[150], x[150], y[150];
void I(int _)
{
k = _;
for (int i = 1; i <= k + 2; ++i)
f[i] = (f[i - 1] + P(i, k)) % M;
}
int Q(int n)
{
x[0] = y[k + 3] = 1;
for (int i = 1; i <= k + 2; ++i)
x[i] = x[i - 1] * (n - i) % M;
for (int i = k + 2; i >= 1; --i)
y[i] = y[i + 1] * (n - i) % M;
if (n <= k + 2)
return f[n];
else
{
int q = 0;
for (int i = 1; i <= k + 2; ++i)
q = (q + f[i] * x[i - 1] % M * y[i + 1] % M * v[i - 1] % M * v[k + 2 - i] % M * (k + 2 - i & 1 ? M - 1 : 1)) % M;
return q;
}
}
} O[150];
int Q(int x, int n)
{
int z = 0;
for (int l = 64; l >= 1; --l)
{
int L = pow(n, 1.0 / (l + 1)) + 1, R = pow(n, 1.0 / l);
R = min(R, x);
if (L > R)
continue;
z = (z + n % M * (l + 1) % M * ((L + R - 2) % M) * ((R - L + 1) / 2)) % M;
z = (z + M - (O[l + 1].Q(R) - O[l + 1].Q(L - 1) - (R - L + 1))) % M;
}
return z;
}
signed main()
{
for (int i = o[0] = 1; i <= 100; ++i)
o[i] = o[i - 1] * i % M;
v[100] = P(o[100], M - 2);
for (int i = 99; i >= 0; --i)
v[i] = v[i + 1] * (i + 1) % M;
for (int i = 1; i <= 100; ++i)
O[i].I(i);
scanf("%lld", &T);
while (T--)
{
scanf("%lld%lld%lld", &l, &r, &n);
int q = (Q(r, n) + M - Q(l - 1, n)) % M;
printf("%lld\n", q);
}
return 0;
}