考虑全体 $n$ 个元素的多重集，且集合中每个数都为 $2^i(i\in (-\infty,0] \cap \mathbb Z)$，请问有多少个集合满足集合内所有数的和等于 $k$？你只需要将答案取模 $998244353$。

输入格式

第一行输入两个正整数 $N,Q$，表示 $n$ 的范围以及询问次数。

接下来 $Q$ 行，每行两个正整数 $n,k$，保证 $n\ge k$。

输出格式

输出 $Q$ 行，每行一个整数表示方案数取模 $998244353$。

样例数据

样例 1 输入

3000000 10
4 1
4 2
4 3
4 4
10 3
100 13
1000 666
100000 99824
1000000 112358
3000000 2999990

样例 1 输出

2
2
1
1
35
69549003
511129129
673402331
520502118
253

子任务

对于 $100\%$ 的数据，保证 $1\le k\le n\le N\le 3\times 10^6$，且 $Q\le 2\times 10^5$。