Alice's potion making professor gave the following assignment to his students: brew a potion using $$$n$$$ ingredients, such that the proportion of ingredient $$$i$$$ in the final potion is $$$r_i \gt 0$$$ (and $$$r_1 + r_2 + \cdots + r_n = 1$$$).

He forgot the recipe, and now all he remembers is a set of $$$n-1$$$ facts of the form, "ingredients $$$i$$$ and $$$j$$$ should have a ratio of $$$x$$$ to $$$y$$$" (i.e., if $$$a_i$$$ and $$$a_j$$$ are the amounts of ingredient $$$i$$$ and $$$j$$$ in the potion respectively, then it must hold $$$a_i/a_j = x/y$$$), where $$$x$$$ and $$$y$$$ are positive integers. However, it is guaranteed that the set of facts he remembers is sufficient to uniquely determine the original values $$$r_i$$$.

He decided that he will allow the students to pass the class as long as they submit a potion which satisfies all of the $$$n-1$$$ requirements (there may be many such satisfactory potions), and contains a positive integer amount of each ingredient.

Find the minimum total amount of ingredients needed to make a potion which passes the class. As the result can be very large, you should print the answer modulo $$$998\,244\,353$$$.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$).

Each of the next $$$n-1$$$ lines contains four integers $$$i, j, x, y$$$ ($$$1 \le i, j \le n$$$, $$$i\not=j$$$, $$$1\le x, y \le n$$$) — ingredients $$$i$$$ and $$$j$$$ should have a ratio of $$$x$$$ to $$$y$$$. It is guaranteed that the set of facts is sufficient to uniquely determine the original values $$$r_i$$$.

It is also guaranteed that the sum of $$$n$$$ for all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, print the minimum total amount of ingredients needed to make a potion which passes the class, modulo $$$998\,244\,353$$$.

Note

In the first test case, the minimum total amount of ingredients is $$$69$$$. In fact, the amounts of ingredients $$$1, 2, 3, 4$$$ of a valid potion are $$$16, 12, 9, 32$$$, respectively. The potion is valid because

Ingredients $$$3$$$ and $$$2$$$ have a ratio of $$$9 : 12 = 3 : 4$$$;
Ingredients $$$1$$$ and $$$2$$$ have a ratio of $$$16 : 12 = 4 : 3$$$;
Ingredients $$$1$$$ and $$$4$$$ have a ratio of $$$16 : 32 = 2 : 4$$$.

In the second test case, the amounts of ingredients $$$1, 2, 3, 4, 5, 6, 7, 8$$$ in the potion that minimizes the total amount of ingredients are $$$60, 60, 24, 48, 32, 60, 45, 30$$$.

Potion Brewing Class

Examples