C. Мистер Б и маяки на поле
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Мистер Б живет в домике посередине огромного плоского поля, и так случилось, что оно заинтересовало инопланетную жизнь. Для удобства инопланетяне определили декартову систему координат таким образом, что домик Мистера Б находится в точке (0, 0). Далее они сбросили систему из трех сигнальных маяков, но не все пошло по плану. Один маяк полостью сгорел в атмосфере, а два другие приземлились в координатах (m, 0) и (0, n), но сломались и отключились.

Мистера Б заинтересовали необычные устройства и он решил приволочь их к себе домой для более детального осмотра. Он пришел за первым маяком, находящемся в (m, 0), взял его и понес к себе домой по кратчайшему пути, потом он пришел за вторым, находящемся в (0, n), и сделал то же самое. При этом, подняв первый маяк, он активировал навигационную систему.

Система, будучи поврежденной, начала работать следующим образом.

В моменты времени, когда оба уцелевших маяка находятся в точках с целочисленными координатами, система пробует найти положение для третьего маяка. Это удается, если существует такая точка с целочисленными координатами, что площадь треугольника, образованного двумя маяками и этой точкой, равна в точности s. В таком случае система посылает пакет информации с координатами маяков инопланетянам, иначе — нет.

Посчитайте, сколько пакетов информации было послано системой инопланетянам в процессе передвижения маяков.

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

В первой строке находится единственное число t (1 ≤ t ≤ 1000) — количество тестовых случаев. В следующих 3·t стоках заданы t тестовых случаев.

Каждый тестовый случай задается в трех строках. Обратите внимание, параметры задачи заданы в виде произведения трех множителей.

В первой строке каждого тестового случая заданы три целых числа: n1, n2 и n3 (1 ≤ ni ≤ 106) такие, что n = n1·n2·n3.

Во второй строке заданы три целых числа: m1, m2, m3 (1 ≤ mi ≤ 106) такие, что m = m1·m2·m3.

Во третьей строке заданы три целых числа: s1, s2, s3 (1 ≤ si ≤ 106) такие, что s = s1·s2·s3.

Обратите внимание, что для взломов разрешены только тесты с t = 1.

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

Выведите t чисел по одному в каждой строке — ответы на каждый тестовый случай.

Пример
Входные данные
3
2 1 1
2 1 1
1 1 3
1 5 1
2 2 1
1 1 2
10 6 18
2 103 2
13 1 13
Выходные данные
4
7
171
Примечание

В первом тестовом случае изначальные позиции маяков следующие: (2, 0) и (0, 2), s = 3. Могли быть посланы следующие пакеты вида (b1, b2, p), где b1 — позиция первого маяка, b2 — позиция второго маяка, p — некоторая третья точка: ((2, 0), (0, 2), ( - 1, 0)), ((1, 0), (0, 2), (4, 0)), ((0, 0), (0, 2), (3, 1)), ((0, 0), (0, 1), ( - 6, 0))

Во втором тестовом случае изначальные позиции маяков следующие: (4, 0) и (0, 5), s = 2. Могли быть посланы следующие пакеты: ((4, 0), (0, 5), (0, 4)), ((3, 0), (0, 5), (2, 3)), ((2, 0), (0, 5), (2, 2)), ((1, 0), (0, 5), (1, 4)), ((0, 0), (0, 4), (0,  - 1)), ((0, 0), (0, 2), (2, 0)), ((0, 0), (0, 1), (4, 0)).