{"scoring":null,"notes":"","legend":"Антон живет в Нодляндии и очень любит музыку. Он выучил нодную грамоту и уже готов сыграть свою любимую сонату Евклида, но у него нет синтезатора. Синтезаторы в Нодляндии особенные~--- у каждого ровно $n$ клавиш, на каждой из которых написана своя нода~--- натуральное число от $1$ до $m$. Чтобы синтезатор звучал круто, $НОД$ всех нод должен быть равен $1$. Например, синтезатор $[52, 6, 18]$~--- звучит не круто ($НОД$ равен 3), а $[4, 6, 3]$~--- круто. Антон, конечно, хочет себе крутой синтезатор, но еще не выбрал, какой именно. Он просит вас посчитать, сколько всего крутых синтезаторов может быть в Нодляндии по модулю $998244353$.\r\n\r\n$НОД$ чисел массива равен максимальному натуральному числу, которое делит все числа в массиве нацело. Например, $НОД([18, 27, 6]) = 3$.","authorLogin":"Skobivan","language":"russian","timeLimit":2000,"output":"Для каждого набора входных данных выведите единственное целое число~--- количество крутых синтезаторов в Нодляндии по модулю $998244353$","inputFile":"stdin","outputFile":"stdout","input":"В первой строке дано целое число $t$ ($1 \\le t \\le 10^4$)~--- количество наборов входных данных.\r\n\r\nДалее следуют описания наборов.\r\n\r\nВ каждой строке даны два целых числа $n$ и $m$ ($1 \\le n, m \\le 2 \\cdot 10^5$)~--- размер синтезаторов и количество нод в Нодляндии.\r\n\r\nГарантируется, что сумма $n$ по всем наборам входных данных не превосходит $2 \\cdot 10^5$.\r\n\r\nГарантируется, что сумма $m$ по всем наборам входных данных не превосходит $2 \\cdot 10^5$.","authorName":"Ivan Skobelev","sampleTests":[{"output":"11\r\n1\r\n241327425","input":"3\r\n2 4\r\n3 1\r\n123 456\r\n","inputFile":"example.01","outputFile":"example.01.a"}],"name":"Соната Евклида","interaction":null,"memoryLimit":268435456,"tutorial":""}