Цукерочки для друзів

Обмеження: 4 сек., 1024 МіБ

Зеник з Марічкою вирішили запросити друзів у гості після виснажливої олімпіади до своїх апартаментів та пригостити їх цукерочками.

У них є $n$ друзів-алгоритмістів. Деякі з них настільки затяті, що не полишають розв’язування задач ні вдень, ні вночі, і будуть сьогодні писати AtCoder Regular Contest. Вони не знають точної кількості друзів, які планують писати це змагання (і не прийдуть через це у гості). Проте вони знають, що таких друзів буде хоча б один, але не більше ніж $k$. Тобто прийняти запрошення Зеника з Марічкою можуть $n-1$, $n-2$, ..., або $n-k$ друзів.

Зеник з Марічкою повинні справити на гостей щонайкраще враження. Вони хочуть купити цукерочки так, аби порівну поділити їх між друзями, скільки б їх не зібралось. Зауважте, що вони не можуть залишити деякі цукерочки собі або роздати їх не порівну, адже це суперечитиме правилам етикету. Тому вони куплять рівно НСК($n-1, n-2, \dots, n-k$) цукерок.

Після того, як Зеник з Марічкою купили цукерочки, вони помітили, що вони цю кількість можуть розділити на всіх $n$ друзів.

Вам відоме значення $k$, але кількість друзів $n$ ви не знаєте. Порахуйте, скільки існує таких значень $n$, що задовольняють умову. Формально, потрібно порахувати кількість натуральних чисел $n > k$ таких, що НСК($n-1, n-2, \dots, n-k$) ділиться націло на $n$. Оскільки ця кількість може бути дуже великою, слід обчислити остачу від ділення її на просте число 998244353.

Зеник і Марічка хочуть, щоб усе пройшло ідеально, тому розглядають $t$ різних значень $k$, для кожного з яких вони просять вас незалежно розв’язати задачу.

Вхідні дані

У першому рядку задано одне ціле число $t$ — кількість запитів.

У наступному рядку задано $t$ цілих чисел $k$, для кожного з яких треба розв’язати задачу.

Вихідні дані

У єдиному рядку виведіть $t$ цілих чисел — відповіді на відповідні запити, тобто кількість цілих чисел $n$, для яких НСК($n-1, n-2, \dots, n-k$) ділиться націло на $n$ за модулем 998244353.

Обмеження

$1 \le t \le 10^5$,

$1 \le k \le 10^7$.

Оцінювання задачі складається із наступних блоків:

1 бал — приклад з умови,

4 бали — $t = 1, k \le 20$,

10 балів — $t = 1, k \le 10^7$,

10 балів — без додаткових обмежень.

Бали за блок ви отримаєте лише якщо дасте правильну відповідь на всі тести з блоку.

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
2 4 101	2 322961306

Примітки

НСК($n-1, n-2, \dots, n-k$) — це найменше спільне кратне, тобто найменше натуральне число, що ділиться націло на $n-1, n-2, \dots, n-k$.

Для $k=4$ умову задовольняють $n=6$ і $n=12$.

• НСК(5, 4, 3, 2) = 60 ділиться на 6.

• НСК(11, 10, 9, 8) = 3960 ділиться на 12.

Для $k=101$ відповідь $322961306 \equiv 1321205659\pmod{998244353}$.