F. Умножительные массивы
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Даны целые числа $$$k$$$ и $$$n$$$. Для каждого целого числа $$$x$$$ от $$$1$$$ до $$$k$$$ посчитайте количество целых массивов $$$a$$$, таких что выполняются все следующие условия:

  • $$$1 \leq |a| \leq n$$$, где $$$|a|$$$ обозначает длину массива $$$a$$$.
  • $$$1 \leq a_i \leq k$$$ для всех $$$1 \leq i \leq |a|$$$.
  • $$$a_1 \times a_2 \times \dots \times a_{|a|}=x$$$ (т.е. произведение всех элементов равно $$$x$$$).

Обратите внимание, что два массива $$$b$$$ и $$$c$$$ различны, если либо их длины различны, либо существует индекс $$$1 \leq i \leq |b|$$$, такой что $$$b_i\neq c_i$$$.

Выведите ответ по модулю $$$998\,244\,353$$$.

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

Первая строка содержит целое число $$$t$$$ ($$$1 \leq t\leq 10^3$$$) — количество наборов входных данных.

Единственная строка каждого набора входных данных содержит два целых числа $$$k$$$ и $$$n$$$ ($$$1 \leq k \leq 10^5, 1\leq n \leq 9\cdot 10^8$$$).

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

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

Для каждого набора входных данных выведите $$$k$$$ целых чисел, разделенных пробелом, на новой строке: количество массивов для $$$x=1,2,\ldots,k$$$, по модулю $$$998\,244\,353$$$.

Пример
Входные данные
3
2 2
4 3
10 6969420
Выходные данные
2 3
3 6 6 10
6969420 124188773 124188773 729965558 124188773 337497990 124188773 50981194 729965558 337497990
Примечание

В первом наборе входных данных существует $$$2$$$ массива $$$a$$$ с $$$|a|\leq 2$$$ и произведением элементов, равным $$$1$$$:

  • $$$[1]$$$
  • $$$[1,1]$$$

Существует $$$3$$$ массива $$$a$$$ с $$$|a|\leq 2$$$ и произведением элементов, равным $$$2$$$:

  • $$$[2]$$$
  • $$$[1,2]$$$
  • $$$[2,1]$$$