D. Посчитайте НОД
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам даны два целых числа $$$n$$$ и $$$m$$$ и массив $$$a$$$ из $$$n$$$ целых чисел. Для каждого $$$1 \le i \le n$$$ верно, что $$$1 \le a_i \le m$$$.

Ваша задача — посчитать количество различных массивов $$$b$$$ длины $$$n$$$ таких, что:

  • $$$1 \le b_i \le m$$$ для каждого $$$1 \le i \le n$$$, и при этом
  • $$$\gcd(b_1,b_2,b_3,...,b_i) = a_i$$$ для каждого $$$1 \le i \le n$$$.

Здесь $$$\gcd(a_1,a_2,\dots,a_i)$$$ обозначает наибольший общий делитель (НОД) целых чисел $$$a_1,a_2,\ldots,a_i$$$.

Так как это число может быть слишком большим, выведите его по модулю $$$998\,244\,353$$$.

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

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит единственное целое число $$$t$$$ ($$$1 \le t \le 100$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$1 \le m \le 10^9$$$) — длину массива $$$a$$$ и максимально возможное значение элемента.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le m$$$) — элементы массива $$$a$$$.

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

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

Для каждого набора входных данных выведите единственное целое число — количество различных массивов, удовлетворяющих приведенным выше условиям. Так как это число может быть большим, выведите его по модулю $$$998\,244\,353$$$.

Пример
Входные данные
5
3 5
4 2 1
2 1
1 1
5 50
2 3 5 2 3
4 1000000000
60 30 1 1
2 1000000000
1000000000 2
Выходные данные
3
1
0
595458194
200000000
Примечание

В первом наборе входных данных допустимыми массивами $$$b$$$ являются:

  • $$$[4,2,1]$$$;
  • $$$[4,2,3]$$$;
  • $$$[4,2,5]$$$.

Во втором наборе входных данных единственным массивом, удовлетворяющим требованиям, является $$$[1,1]$$$.

В третьем наборе входных данных можно доказать, что такого массива не существует.

В третьем и четвертом тестовых примерах есть красивые объяснения, но, к сожалению, они слишком длинные, чтобы их писать, поэтому мы просим вас поверить нам.