Имеется $n$ групп предметов, где $i$-я группа содержит $a_i$ предметов, и каждый предмет имеет вес $2^{b_i}$. Также имеется $m$ рюкзаков, каждый вместимостью $k$. Вычислите наименьшее $k$, при котором возможно поместить все $\sum_{i=1}^n a_i$ предметов в рюкзаки так, чтобы суммарный вес предметов в каждом рюкзаке не превышал $k$.

Заметьте, что каждый предмет должен быть помещен ровно в один рюкзак. Один рюкзак может содержать предметы из разных групп, а предметы из одной группы могут быть распределены по разным рюкзакам.

Входные данные

Имеется несколько тестовых случаев. Первая строка входных данных содержит целое число $T$ ($1 \le T \le 10^4$), указывающее количество тестовых случаев. Для каждого тестового случая:

Первая строка содержит два целых числа $n$ и $m$ ($1 \le n \le 2 \times 10^5$, $1 \le m \le 10^9$), указывающие количество групп предметов и количество рюкзаков.

В следующих $n$ строках $i$-я строка содержит два целых числа $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$.

Выходные данные

Для каждого тестового случая выведите одну строку, содержащую одно целое число — ответ. Так как ответ может быть большим, выведите его по модулю $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