Ву проголодался после интенсивной тренировки и отправился в ближайший магазин, чтобы приобрести его любимую лапшу быстрого приготовления. После того, как Ву расплатился, кассир задал ему интересную задачу.
Дан двудольный граф, в вершинах правой доли которого записаны положительные целые числа. Для подмножества вершин \(S\) левой доли определим \(N(S)\) как множество вершин правой доли, смежной хотя бы с одной из вершин \(S\), а \(f(S)\) — как сумму чисел, записанных в вершинах \(N(S)\). Требуется найти наибольший общий делитель чисел \(f(S)\) для всех возможных непустых подмножеств \(S\) (полагайте, что НОД пустого множества равен \(0\)).
Ву слишком устал во время тренировки, чтобы справиться с такой задачей. Помогите ему!
Выходные данные
Для каждого тестового случая выведите единственное число — искомый наибольший общий делитель.
Примечание
Наибольшим общим делителем множества чисел называется наибольшее целое число \(g\) такое, что все элементы множества без остатка делятся на \(g\).
В первом примере все вершины левой доли соединены ребром со всеми вершинами правой доли, поэтому значение \(f(S)\) для любого непустого подмножества будет равно \(2\), соответственно наибольший общий делитель этих значений будет также равен \(2\).
Во втором примере подмножество \(\{1\}\) вершин левой доли соединено ребром с вершинами \(\{1, 2\}\) правой доли, сумма значений в которых равна \(2\), а подмножество \(\{1, 2\}\) вершин левой доли соединено рёбрами с вершинами \(\{1, 2, 3\}\) правой доли, сумма значений в которых равна \(3\). Таким образом, \(f(\{1\}) = 2\), \(f(\{1, 2\}) = 3\), что значит, что наибольший общий делитель всех чисел \(f(S)\) равен \(1\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
2 4
1 1
1 1
1 2
2 1
2 2
3 4
1 1 1
1 1
1 2
2 2
2 3
4 7
36 31 96 29
1 2
1 3
1 4
2 2
2 4
3 1
4 3
|
2
1
12
|