E. Соната Евклида
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Антон живет в Нодляндии и очень любит музыку. Он выучил нодную грамоту и уже готов сыграть свою любимую сонату Евклида, но у него нет синтезатора. Синтезаторы в Нодляндии особенные — у каждого ровно $$$n$$$ клавиш, на каждой из которых написана своя нода — натуральное число от $$$1$$$ до $$$m$$$. Чтобы синтезатор звучал круто, $$$НОД$$$ всех нод должен быть равен $$$1$$$. Например, синтезатор $$$[52, 6, 18]$$$ — звучит не круто ($$$НОД$$$ равен 3), а $$$[4, 6, 3]$$$ — круто. Антон, конечно, хочет себе крутой синтезатор, но еще не выбрал, какой именно. Он просит вас посчитать, сколько всего крутых синтезаторов может быть в Нодляндии по модулю $$$998244353$$$.

$$$НОД$$$ чисел массива равен максимальному натуральному числу, которое делит все числа в массиве нацело. Например, $$$НОД([18, 27, 6]) = 3$$$.

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

В первой строке дано целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.

Далее следуют описания наборов.

В каждой строке даны два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n, m \le 2 \cdot 10^5$$$) — размер синтезаторов и количество нод в Нодляндии.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

Гарантируется, что сумма $$$m$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

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

Для каждого набора входных данных выведите единственное целое число — количество крутых синтезаторов в Нодляндии по модулю $$$998244353$$$

Пример
Входные данные
3
2 4
3 1
123 456
Выходные данные
11
1
241327425