$n$ 個のアイテムのグループがあり、$i$ 番目のグループには $a_i$ 個のアイテムが含まれており、各アイテムの重さは $2^{b_i}$ です。 また、$m$ 個のナップサックがあり、それぞれの容量は $k$ です。すべての $\sum_{i=1}^n a_i$ 個のアイテムをナップサックに入れ、かつ各ナップサック内のアイテムの合計重量が $k$ を超えないようにすることが可能な最小の $k$ を計算してください。

各アイテムは必ずちょうど1つのナップサックに入れなければならないことに注意してください。1つのナップサックに異なるグループのアイテムが含まれてもよく、同じグループのアイテムが異なるナップサックに分けられても構いません。

入力

入力は複数のテストケースから構成されます。入力の最初の行には、テストケースの数を示す整数 $T$ ($1 \le T \le 10^4$) が含まれます。各テストケースは以下の形式です。

最初の行には、アイテムのグループ数とナップサックの数を示す2つの整数 $n$ と $m$ ($1 \le n \le 2 \times 10^5, 1 \le m \le 10^9$) が含まれます。

続く $n$ 行のうち $i$ 番目の行には、2つの整数 $a_i$ と $b_i$ ($1 \le a_i \le 10^9, 0 \le b_i \le 10^9$) が含まれます。ここで $a_i$ は $i$ 番目のグループのアイテム数、$2^{b_i}$ は $i$ 番目のグループの各アイテムの重さです。

すべてのテストケースにおける $n$ の総和は $2 \times 10^5$ を超えないことが保証されています。

出力

各テストケースについて、答えを示す整数を1行に出力してください。答えは非常に大きくなる可能性があるため、$998\,244\,353$ で割った余りを出力してください。ここで用いる法は出力の簡略化のみを目的としており、法を適用する前に答えを最小化する必要があることに注意してください。

入出力例

入出力例 1

2
5 4
3 0
2 3
3 1
1 3
2 1
2 20250427
1000000000 1000000000
114514 1919810

入出力例 1

10
628956724