8558: Find different

You are given two integers $n$,$m$.

Two array x=x0,x1,…,xl−1,y=y0,y1,…, yl−1 of length $l$ are considered different if $x$ couldn't become $y$ by performing the following operations any number of times:

 operation 1$:$ Change $x$ to $b$ , for each bi = (xi+1) mod m

operation 2$:$ Change $x$ to $b$ , for each bi = x(i+1) mod l

As an example, if $m=3,l=3$, $(0,2,2)$ and $0,1,0)$ are considered not different because $(0,2,2)$ can become $(0,1,0)$ as follows: 

(0,2,2)⟶operation 1(1,0,0)⟶operation 2(0,0,1)⟶operation 2(0,1,0)

For each i, find the number of different integer array a of length i satisfied ∀j∈(0,1,…,i−1),0≤aj≤m−1.

Since the answer may be too large, print it modulo 998244353.

The first line of the input contains one integer T $($$1\le T\le 100$$)$--- the number of test cases. Then T testcases follow.

Each of the next T lines contains two integers n,m $1\le n,m\le 100000$$)$.

The sum of n over all testcases doesn't exceed 106.

2
10 2
10 100000

1 2 2 4 4 8 10 20 30 56
1 50001 338600275 682529035 345997022 799071125 767573961 525777344 672451750 695859947