Mister B and Beacons on Field

题意翻译

外星人盯上了Farmer Jack的农场！我们假设FJ的农场是一个二维直角坐标系，FJ的家在原点。外星人向FJ的农场上投放了3个信标，不幸的是，有一个信标落地就完全损坏了，且不知道具体位置，其余两个信标分别被投放到了 $(m,0)​$ 和 $(0,n)$ 处。 FJ对这些新的金闪闪的东西很感兴趣，他决定将这两个信标搬到家里去。具体地，FJ先从 $(0,0)$ 沿着 $x$ 轴走到 $(m,0)$ ，捡起信标，然后沿着 $x$ 轴返回 $(0,0)$ ，把信标放到家中。再从 $(0,0)$ 沿着 $y$ 轴走到 $(0,n)$ ，捡起信标，然后沿着 $y$ 轴返回 $(0,0)$ ，把信标放到家中。 然而那两个没有损坏的信标在一直与外星人保持联系，它们一直在试图寻找那个损坏的信标的位置。具体地，当两个未损坏的信标的坐标都是整数时，如果存在平面上的一个整点，满足这个点与两个未损坏的信标组成的三角形面积为 $s$ ，则两个信标会向外星人发送一次信息。现在外星人想知道，在搬运的整个过程中，这两个信标一共会向外星人发送多少次信息？ t组数据，$n=n_1\cdot n_2\cdot n_3$,$m,s$同理，$n_1,n_2,n_3...\le 10^6$

题目描述

Mister B has a house in the middle of a giant plain field, which attracted aliens life. For convenience, aliens specified the Cartesian coordinate system on the field in such a way that Mister B's house has coordinates $ (0,0) $ . After that they sent three beacons to the field, but something went wrong. One beacon was completely destroyed, while the other two landed in positions with coordinates $ (m,0) $ and $ (0,n) $ , respectively, but shut down. Mister B was interested in this devices, so he decided to take them home. He came to the first beacon, placed at $ (m,0) $ , lifted it up and carried the beacon home choosing the shortest path. After that he came to the other beacon, placed at $ (0,n) $ , and also carried it home choosing the shortest path. When first beacon was lifted up, the navigation system of the beacons was activated. Partially destroyed navigation system started to work in following way. At time moments when both survived beacons are at points with integer coordinates the system tries to find a location for the third beacon. It succeeds if and only if there is a point with integer coordinates such that the area of the triangle formed by the two survived beacons and this point is equal to $ s $ . In this case the system sends a packet of information with beacon positions to aliens, otherwise it doesn't. Compute how many packets of information system sent while Mister B was moving the beacons.

输入输出格式

输入格式

The first line contains one integer $ t $ ( $ 1<=t<=1000 $ ) — the number of test cases. The next $ 3·t $ lines describe $ t $ test cases. Every test case is described in three lines as follows. Note that each parameter is given as a product of three factors. The first line of a test case contains three space-separated integers: $ n_{1} $ , $ n_{2} $ , $ n_{3} $ ( $ 1<=n_{i}<=10^{6} $ ) such that $ n=n_{1}·n_{2}·n_{3} $ . The second line contains three space-separated integers: $ m_{1} $ , $ m_{2} $ , $ m_{3} $ ( $ 1<=m_{i}<=10^{6} $ ) such that $ m=m_{1}·m_{2}·m_{3} $ . The third line contains three space-separated integers: $ s_{1} $ , $ s_{2} $ , $ s_{3} $ ( $ 1<=s_{i}<=10^{6} $ ) such that $ s=s_{1}·s_{2}·s_{3} $ . Note that for hacks only tests with $ t=1 $ allowed.

输出格式

Print $ t $ integers one per line — the answers for each test.

输入输出样例

输入样例 #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

说明

First test case contains the following beacon positions: $ (2,0) $ and $ (0,2) $ , $ s=3 $ . The following packets could be sent: $ ((2,0),(0,2),(-1,0)) $ , $ ((1,0),(0,2),(4,0)) $ , $ ((0,0),(0,2),(3,1)) $ , $ ((0,0),(0,1),(-6,0)) $ , where $ (b_{1},b_{2},p) $ has next description: $ b_{1} $ — first beacon position, $ b_{2} $ — second beacon position, $ p $ — some generated point. Second test case contains the following beacon initial positions: $ (4,0) $ and $ (0,5) $ , $ s=2 $ . The following packets could be sent: $ ((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)) $ .