P12021 面包题

面包（bread）

从 $1 \sim n$ 的自然数中选出若干个数（可以不选），满足以下条件： - 若选择了 $x$，则不能选择 $kx$。 求总共有多少种选法（不考虑顺序）。 答案需要**对** ${998244353}$ **取模**。

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

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

### 样例解释 对于第一组数据，满足条件的 $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$