import sys
from heapq import *
input = sys.stdin.readline

ans = []
MOD = 998244353
LEN = 10 ** 6
ITs = []

def iter_z(base: int, c: int):
    x = 0
    for L in range(1, 100000):
        x *= base
        x += c
        yield x

q = []
def push(it: int):
    x = next(ITs[it])
    heappush(q, (x, it))

for base in range(2, 17):
    for c in range(1, base):
        if (base, c) in {(4, 3), (8, 7), (9, 4), (9, 8), (16, 5), (16, 10), (16, 15)}:
            continue
        it = len(ITs)
        ITs.append(iter_z(base, c))
        push(it)

ans = []
prev = 0
while len(ans) < LEN:
    x, it = heappop(q)
    x %= MOD
    push(it)
    if x == prev:
        continue
    prev = x
    ans.append(x)

ans.insert(0, 0)
for i in range(LEN):
    ans[i + 1] += ans[i]

for _ in range(int(input())):
    L, R = map(int, input().split())
    print((ans[R] - ans[L - 1]) % MOD)

answer.code:1:1: error: ‘import’ does not name a type
    1 | import sys
      | ^~~~~~
answer.code:1:1: note: C++20 ‘import’ only available with ‘-fmodules-ts’, which is not yet enabled with ‘-std=c++20’
answer.code:24:86: error: expected unqualified-id before ‘:’ token
   24 |         if (base, c) in {(4, 3), (8, 7), (9, 4), (9, 8), (16, 5), (16, 10), (16, 15)}:
      |                                                                                      ^