Расследование убийства

Эркюль Пуаро --- известный детектив. Как вы знаете, сегодня в поезде, в котором Пуаро ехал по своим делам, был убит человек. Эркюль пытается разгадать, кто это сделал. Для этого ему необходимо узнать, на каком месте в поезде сидел этот человек.

Пуаро заподозрил $q$ людей. $i$-й из них сидит на месте $n\_i$, $k\_i$. Чтобы понять, может ли $i$-й человек быть преступником, Эркюль должен вычислить коэффициент злодейства человека $i$. Формулы почти вычислены, осталось лишь подставить числа хитрости для мест, на которых сидят подозреваемые.

Число хитрости места $n$, $k$ --- $\beta(n, k)$ может быть вычислено по следующим правилам:

\begin{equation\*} \beta(n, k) = \begin{cases} 1 &\text{если $n = 0$}\\\ k \cdot \frac{\beta(0, k) + \beta(1, k) + \ldots + \beta(n - 1, k)}{n} &\text{если $n \ge 1$} \end{cases} \end{equation\*}

Так как числа хитрости могут быть достаточно большими, выведите их значение по модулю $998244353$. Обратите внимание, что взятие по модулю следует производить только при выводе ответа, а не в процессе вычисления.

В первой строке входного файла записано число $q$ --- количество подозреваемых ($1 \le q \le 2 \cdot 10^5$).

В $i$-й из следующих $q$ строк записаны два числа $n\_i$ и $k\_i$, характеризующие место, на котором сидит человек $i$ ($1 \le i \le q$, $1 \le n\_i, k\_i \le 2 \cdot 10^5$).

Выведите $q$ строк. В $i$-й строке единственное число --- число хитрости места, на котором сидит $i$-й человек, по модулю $998244353$.