题目背景

面包（bread）

题目描述

从 $1 \sim n$ 的自然数中选出若干个数（可以不选），满足以下条件：

• 若选择了 $x$，则不能选择 $kx$。

求总共有多少种选法（不考虑顺序）。

答案需要对 ${998244353}$ 取模。

输入格式

第一行一个正整数 $T$ 表示数据组数。

接下来每组数据一行输入两个正整数：$n,k$，含义同题面所示。

输出格式

一共 $T$ 行，每行一个正整数表示对应的答案。

3
4 2
2 2
10 20

10
3
1024

提示

样例解释

对于第一组数据，满足条件的 $S$ 有 $\varnothing,\{1\},\{1,3\},\{1,4\},\{1,3,4\},\{2\},\{2,3\},\{3\},\{3,4\},\{4\}$，共 $10$ 种 $S$ 满足上述条件。

对于第二组数据，满足条件的 $S$ 有 $\varnothing,\{1\},\{2\}$，共 $3$ 种 $S$ 满足上述条件。

对于第三组数据，任意满足 $S\subseteq\{1,2,3,\dots,10\}$ 的 $S$ 都符合条件，因此答案为 $2^{10}=1024$。

数据范围

对于 $20\%$ 的数据：$1\leq T\leq 10$，$2\leq n,k \leq 15$

对于 $40\%$ 的数据：$1\leq T\leq 10^2$，$2\leq n,k \leq 10^5$

对于 $100\%$ 的数据：$1\leq T\leq 10^5$，$2\leq n,k \leq 10^9$