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

Обмеження: 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}\).