Description

求有多少个本质不同长度为 $n$ 的由 $0$ 和 $1$ 构成的环，满足环上任意一段长度为 $k$ 的子段和均相等。

Input

第一行一个整数 $T\ (1\leq T\leq 10^5)$，为数据组数。

接下来 $T$ 行每行两个整数 $n,k\ (2\leq n \leq 10^6,1\leq k <n)$，意义如题目描述。

Output

输出 $T$ 行，对于每组数据输出一行一个整数，表示本质不同且满足条件的 01 环个数，因为答案过大，只要求输出答案模 $998244353$ 后的结果。

Samples

4
2 1
4 2
10 6
100 10

2
3
3
108

Note

循环同构的环在这里被认为是本质相同的，如 $01$ 与 $10$，$00110$ 与 $01100$ 都被认为是同构的，只能计算一次贡献。

Resources

The 21st UESTC Programming Contest Preliminary