Với hai số nguyên dương ~n~ và ~m~ bất kỳ, định nghĩa giá trị của ~f(n,m)~ như sau:

• Xét dãy số ~a~ gồm ~n~ phần tử, ban đầu ~a_i=0~ với mọi ~i~ từ ~1~ đến ~n~.

• Thực hiện thao tác sau đúng ~m~ lần: Chọn một chỉ số ~i~ ngẫu nhiên từ ~1~ đến ~n~, sau đó tăng ~a_i~ lên ~1~ đơn vị. Trong mỗi thao tác, mỗi chỉ số đều có xác suất được chọn là ~\frac{1}{n}~.

• Khi đó, ~f(n,m)~ là xác suất để sau khi thực hiện các thao tác, dãy ~a~ là độ dài các cạnh của một đa giác lồi gồm ~n~ đỉnh.

Bạn được cho hai số nguyên dương ~n~ và ~k~. Nhiệm vụ của bạn là xác định giá trị của ~f(n,n), f(n,n+1), \dots, f(n,n+k-1)~ khi chia dư cho ~998\,244\,353~.

Input

Dòng đầu tiên chứa số lượng test case ~t~ (~1 \le t \le 50\,000~). Mô tả của mỗi test case như sau:

Dòng đầu tiên và duy nhất của test case chứa hai số nguyên dương ~n~ và ~k~ (~3\le n\le 150\,000, 1\le k\le 150\,000~).

Dữ liệu đảm bảo tổng ~n~ và tổng ~k~ trong tất cả test case không vượt quá ~150\,000~.

Output

Với mỗi test case, in ra lần lượt ~k~ số nguyên ~f(n,n), f(n,n+1), \dots, f(n,n+k-1)~, modulo ~998\,244\,353~. Cụ thể, nếu đáp án được biểu diễn dưới dạng phân số tối giản ~\frac{p}{q}~, in ra số nguyên không âm ~s<998\,244\,353~ sao cho ~q\cdot s=p \pmod{998\,244\,353}~.

Scoring

Sample Input 1

2
3 4
4 7

Sample Output 1

887328314 0 813384288 271128096 
904658945 764280833 735035393 537628673 550423553 364897793 394485953

Notes

Với ~n=3~ và ~m=3~, dãy duy nhất có thể được tạo ra và thỏa mãn điều kiện đề bài là ~\{1,1,1\}~. Xác suất tạo ra dãy này là ~\frac{6}{27}~. Do đó, ~f(3,3)=\frac{6}{27}~. Chương trình cần in ra ~887\,328\,314~ do ~887\,328\,314\times 27=6 \pmod{998\,244\,353}~.

Với ~n=3~ và ~m=4~, có thể tạo ra nhiều dãy khác nhau, nhưng không có dãy nào thỏa mãn các phần tử là độ dài ba cạnh của một tam giác. Do đó, ~f(3,4)=0~.

Với ~n=3~ và ~m=5~, có ba dãy thỏa mãn điều kiện đề bài là ~\{1,2,2\}~, ~\{2,1,2\}~ và ~\{2,2,1\}~. Xác suất tạo ra mỗi dãy đều bằng ~\frac{10}{81}~. Do đó, ~f(3,5)=3\times \frac{10}{81}=\frac{10}{27}~. Chương trình cần in ra ~813\,384\,288~ do ~813\,384\,288\times 27=10 \pmod{998\,244\,353}~.

Với ~n=3~ và ~m=6~, dãy duy nhất có thể được tạo ra và thỏa mãn điều kiện đề bài là ~\{2,2,2\}~. Xác suất tạo ra dãy này là ~\frac{10}{81}~. Do đó, ~f(3,6)=\frac{10}{81}~. Chương trình cần in ra ~271\,128\,096~ do ~271\,128\,096\times 81=10 \pmod{998\,244\,353}~.