import sys

from collections import defaultdict, deque, Counter
from heapq import heapify, heappush, heappop, merge
from bisect import bisect_right, bisect_left 
left_binser = lower_bound = bisect_left ; right_binser = upper_bound = bisect_right
from itertools import permutations, combinations, accumulate

# from math import lcm,gcd
# from math import comb, perm
# from functools import lru_cache
# from types import GeneratorType

MOD = 10**9 + 7
_MOD = 998244353

YES = "YES"
NO = "NO"
ALICE = "Alice"
BOB = "Bob"

def FLOOR_DIV(a, b) :
    return a // b
def CEIL_DIV(a, b) :
    return (a // b) + (not(not(a % b)))

def get() :
    return map(int, sys.stdin.readline().split())
def getone() :
    return int(sys.stdin.readline().strip())
def getstr() :
    return sys.stdin.readline().split()
def getonestr() :
    return sys.stdin.readline().strip()
def getarr() :
    return list(map(int, sys.stdin.readline().split()))

def _3d_ARRAY_SPAWN(i, j, k) :
    return [[[0 for _k in range(k)] for _j in range(j)] for _i in range(i)]
def _2d_ARRAY_SPAWN(i, j) :
    return [[0 for _j in range(j)] for _i in range(i)]
   
"""
"never doubt that u can't do this, cause it's an insult to ur determination"
by @deepakgoswami0552 10/03/2024
""" 

                                    
def solve() :
    ...
    # Solution here!
    n, k = get()
    if k > n : return 1
    pfs = [1]*(k)
    for i in range(k, n + 1) :
        pfs.append((pfs[-1] + pfs[i - k]) % _MOD)
    return pfs[-1]

""""""
testcase = ""
# testcase = "multiple" # Multiple tc


if testcase == "multiple" :

    for i in range(int(input())) : 
        print(solve())
        # solve()
        ...
else :
    print(solve())
    # solve()
    ...