← 返回题目列表

Codeforces · 819/C

C. B先生和现场的信标

中文机器翻译题面 查看原题

B先生在一片巨大的平原中央有一座房子,吸引了外星人的生命。为了方便起见,外星人在场上指定了笛卡尔坐标系,B先生的房子坐标为(0, 0)。之后他们向现场发送了三个信标,但出现了问题。其中一个信标被完全摧毁,而另外两个信标分别降落在坐标为(m,0)和(0,n)的位置,但已关闭。

B先生对这个设备很感兴趣,所以他决定把它们带回家。他来到位于 (m, 0) 的第一个灯塔,将其举起并选择最短路径将灯塔带回家。之后,他来到位于 (0, n) 的另一个灯塔,并选择最短路径将其带回家。当第一个信标升起时,信标的导航系统被激活。

部分损坏的导航系统开始按以下方式工作。

当两个幸存的信标位于具有整数坐标的点时,系统尝试找到第三个信标的位置。当且仅当存在一个具有整数坐标的点,使得两个幸存的信标和该点形成的三角形的面积等于 s 时,它才会成功。在这种情况下,系统会向外星人发送带有信标位置的信息包,否则不会。

计算 B 先生移动信标时信息系统发送了多少数据包。

输入

第一行包含一个整数 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。

请注意,对于 hacks,仅允许 t = 1 的测试。

输出

每行打印 t 个整数 — 每个测试的答案。

示例

输入 #1

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

输出 #1

4
7
171

注意

第一个测试用例包含以下信标位置:(2, 0) 和 (0, 2),s = 3。可以发送以下数据包:((2, 0), (0, 2), ( - 1, 0)), ((1, 0), (0, 2), (4, 0)), ((0, 0), (0, 2), (3, 1)), ((0, 0), (0, 1), ( - 6, 0)),其中 (b1, b2, p) 具有以下描述:b1 - 第一个信标位置,b2 - 第二个信标位置,p - 某个生成点。

第二个测试用例包含以下信标初始位置:(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))。