D. Урок зельеварения
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Профессор зельеварения дал следующее задание студентам: сварить зелье, используя $$$n$$$ ингредиентов, так, чтобы доля ингредиента $$$i$$$ в зелье равнялась бы $$$r_i > 0$$$ (при этом $$$r_1 + r_2 + \cdots + r_n = 1$$$).

К сожалению, он забыл рецепт зелья, и теперь только помнит набор из $$$n-1$$$ факта вида «ингредиенты $$$i$$$ и $$$j$$$ должны входить в отношении $$$x$$$ к $$$y$$$» (т. е. если за $$$a_i$$$ и $$$a_j$$$ обозначить объемы ингредиентов $$$i$$$ и $$$j$$$ в зелье соответственно, то должно выполняться $$$a_i/a_j = x/y$$$), где $$$x$$$ и $$$y$$$ — положительные целые числа. Гарантируется, что данный набор фактов достаточен, чтобы однозначно определить доли ингредиентов в рецепте $$$r_i$$$.

Профессор решил, что он зачтет задание студентам, если они приготовят зелье, удовлетворяющее всем $$$n-1$$$ ограничениям (таких зелий может быть много), и при этом объем каждого ингредиента строго положительный и выражается целым числом.

Найдите минимальный суммарный объем всех ингредиентов, необходимый, чтобы сварить подходящее зелье. Так как ответ может быть большим, выведите его остаток от деления на $$$998\,244\,353$$$.

Входные данные

Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.

Первая строка каждого набора содержит одно целое число $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$).

Каждая из следующих $$$n-1$$$ строк содержит четыре целых числа $$$i, j, x, y$$$ ($$$1 \le i, j \le n$$$, $$$i\not=j$$$, $$$1\le x, y \le n$$$), обозначающие, что ингредиенты $$$i$$$ и $$$j$$$ должны иметь отношение объемов $$$x$$$ к $$$y$$$. Гарантируется, что этот набор фактов достаточен, чтобы однозначно определить исходные доли $$$r_i$$$.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите минимальный суммарный объем ингредиентов, необходимый, чтобы сделать зелье, подходящее под требования профессора, по модулю $$$998\,244\,353$$$.

Пример
Входные данные
3
4
3 2 3 4
1 2 4 3
1 4 2 4
8
5 4 2 3
6 4 5 4
1 3 5 2
6 8 2 1
3 5 3 4
3 2 2 5
6 7 4 3
17
8 7 4 16
9 17 4 5
5 14 13 12
11 1 17 14
6 13 8 9
2 11 3 11
4 17 7 2
17 16 8 6
15 5 1 14
16 7 1 10
12 17 13 10
11 16 7 2
10 11 6 4
13 17 14 6
3 11 15 8
15 6 12 8
Выходные данные
69
359
573672453
Примечание

В первом наборе входных данных минимальный объем ингредиентов равен $$$69$$$. Действительно, объемы ингредиентов $$$1, 2, 3, 4$$$ должны быть равны $$$16, 12, 9, 32$$$, соответственно. Это зелье подходит, потому что

  • Ингредиенты $$$3$$$ и $$$2$$$ имеют отношение $$$9 : 12 = 3 : 4$$$;
  • Ингредиенты $$$1$$$ и $$$2$$$ имеют отношение $$$16 : 12 = 4 : 3$$$;
  • Ингредиенты $$$1$$$ и $$$4$$$ имеют отношение $$$16 : 32 = 2 : 4$$$.

Во втором наборе объемы ингредиентов $$$1, 2, 3, 4, 5, 6, 7, 8$$$ в зелье минимального суммарного объема равны $$$60, 60, 24, 48, 32, 60, 45, 30$$$.