$n$ 個の要素からなる多重集合を考えます。ただし、集合内の各数は $2^i$ ($i \in (-\infty, 0] \cap \mathbb{Z}$) の形をしています。集合内のすべての数の和が $k$ となるような集合は何通りあるでしょうか。答えを $998244353$ で割った余りを求めてください。

入力

1 行目に、$n$ の範囲とクエリの回数を表す 2 つの正整数 $N, Q$ が与えられます。

続く $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

2
2
1
1
35
69549003
511129129
673402331
520502118
253

小課題

すべてのデータにおいて、$1 \le k \le n \le N \le 3 \times 10^6$ かつ $Q \le 2 \times 10^5$ を満たします。