Istnieje $n$ grup przedmiotów, gdzie $i$-ta grupa zawiera $a_i$ przedmiotów, a każdy przedmiot ma wagę $2^{b_i}$. Istnieje również $m$ plecaków, każdy o pojemności $k$. Oblicz najmniejsze $k$ takie, że możliwe jest umieszczenie wszystkich $\sum_{i=1}^{n} a_i$ przedmiotów w plecakach, a łączna waga przedmiotów w każdym plecaku nie przekracza $k$.

Zauważ, że każdy przedmiot powinien zostać umieszczony w dokładnie jednym plecaku. Jeden plecak może zawierać przedmioty z różnych grup, a przedmioty z tej samej grupy mogą trafić do różnych plecaków.

Wejście

Dostępnych jest wiele zestawów danych testowych. Pierwsza linia wejścia zawiera liczbę całkowitą $T$ ($1 \le T \le 10^4$) określającą liczbę zestawów danych. Dla każdego zestawu danych:

Pierwsza linia zawiera dwie liczby całkowite $n$ oraz $m$ ($1 \le n \le 2 \times 10^5$, $1 \le m \le 10^9$) określające liczbę grup przedmiotów oraz liczbę plecaków.

W kolejnych $n$ liniach, $i$-ta linia zawiera dwie liczby całkowite $a_i$ oraz $b_i$ ($1 \le a_i \le 10^9$, $0 \le b_i \le 10^9$), gdzie $a_i$ to liczba przedmiotów w $i$-tej grupie, a $2^{b_i}$ to waga każdego przedmiotu w $i$-tej grupie.

Gwarantuje się, że suma $n$ dla wszystkich zestawów danych nie przekracza $2 \times 10^5$.

Wyjście

Dla każdego zestawu danych wypisz w jednej linii liczbę całkowitą będącą odpowiedzią. Ponieważ odpowiedź może być duża, wypisz ją modulo $998\,244\,353$. Zauważ, że modulo służy tutaj jedynie uproszczeniu formatu wyjściowego, a Ty musisz zminimalizować wartość odpowiedzi przed wykonaniem operacji modulo.

Przykład

Wejście 1

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

Wyjście 1

10
628956724