Since Jily's first birthday, Zhily has given him a colored string as a gift each year, and each year's gift has been different from all previous ones. This year, Jily was amazed to discover that he has received every possible distinct gift!

We call a colored string that meets the following conditions valid:

It consists of $$$m$$$ types of characters, with exactly $$$n_i$$$ characters of the $$$i$$$-th type;
Each character of the $$$i$$$-th type is colored with one of $$$c_i$$$ colors;
The string can be reduced to an empty string by repeatedly deleting $$$d_i$$$ consecutive characters of the $$$i$$$-th type that share the same color.

Calculate the number of all valid colored strings, modulo $$$998\,244\,353$$$.

Two colored strings are considered different if they differ in at least one position (either in character type or in color).

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains a single integer $$$m$$$ ($$$1\le m\le 2\cdot 10^5$$$) — the number of types.

The $$$i$$$-th of the next $$$m$$$ lines contains $$$n_i, c_i, d_i$$$ ($$$1\le c_i \lt 998\,244\,353, 1\le n_i, d_i \le 10^8$$$) — the total count of characters of the $$$i$$$-th type, the number of colors for this type, and the required reduction length, respectively.

It is guaranteed that the sum of $$$\left\lceil\frac{n_i}{d_i}\right\rceil$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, output one integer in one line, representing the number of valid colored strings, modulo $$$998\,244\,353$$$.

Note

For the examples, let's number all the colors by $$$1, 2, \ldots, \sum_{j=1}^m c_j$$$. Where the colors $$$1+\sum_{j=1}^{i-1} c_j,\ldots,\sum_{j=1}^i c_j$$$ are of the $$$i$$$-th type. Below, the color $$$1, 2, 3$$$ are colored red, blue, and green, respectively.

For the first test case, the valid strings are:

$$$[{\color{red}1}, {\color{red}1}, {\color{blue}2}]$$$
$$$[{\color{red}1}, {\color{red}1}, {\color{green}3}]$$$
$$$[{\color{red}1}, {\color{blue}2}, {\color{red}1}]$$$
$$$[{\color{red}1}, {\color{green}3}, {\color{red}1}]$$$
$$$[{\color{blue}2}, {\color{red}1}, {\color{red}1}]$$$
$$$[{\color{green}3}, {\color{red}1}, {\color{red}1}]$$$

For any of these strings, we can first remove the only $$$2$$$ or $$$3$$$, and then remove the $$$2$$$ consecutive $$$1$$$s.

For the second test case, the valid strings are:

$$$[{\color{red}1}, {\color{red}1}, {\color{green}3}, {\color{green}3}]$$$
$$$[{\color{red}1}, {\color{green}3}, {\color{green}3}, {\color{red}1}]$$$
$$$[{\color{blue}2}, {\color{blue}2}, {\color{green}3}, {\color{green}3}]$$$
$$$[{\color{blue}2}, {\color{green}3}, {\color{green}3}, {\color{blue}2}]$$$
$$$[{\color{green}3}, {\color{red}1}, {\color{red}1}, {\color{green}3}]$$$
$$$[{\color{green}3}, {\color{blue}2}, {\color{blue}2}, {\color{green}3}]$$$
$$$[{\color{green}3}, {\color{green}3}, {\color{red}1}, {\color{red}1}]$$$
$$$[{\color{green}3}, {\color{green}3}, {\color{blue}2}, {\color{blue}2}]$$$

For the third test case, it can be easily seen that there are no valid strings.

Zhily and Colorful Strings

Examples