English · Original
Chinese · Translation
Formal · Original
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.
## Input
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_ ≤ 106) 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_ ≤ 106) 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_ ≤ 106) such that _s_ = _s_1·_s_2·_s_3.
**Note that for hacks only tests with _t_ = 1 allowed.**
## Output
Print _t_ integers one per line — the answers for each test.
[samples]
## Note
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)).
Mister B 的房子位于一片巨大平原的中心，吸引了外星生命。为方便起见，外星人在平原上建立了笛卡尔坐标系，使得 Mister B 的房子位于坐标 #cf_span[(0, 0)]。随后，他们向该平原发送了三个信标，但出了些问题：其中一个信标完全被毁，另外两个分别降落在坐标 #cf_span[(m, 0)] 和 #cf_span[(0, n)] 的位置并关闭了电源。
Mister B 对这些设备很感兴趣，决定把它们带回家。他先来到位于 #cf_span[(m, 0)] 的第一个信标，将其拾起并沿最短路径带回家中。接着，他前往位于 #cf_span[(0, n)] 的第二个信标，也沿最短路径将其带回家中。当第一个信标被拾起时，信标的导航系统被激活。
部分损坏的导航系统以如下方式工作：
在两个幸存信标均位于整数坐标点的时刻，系统尝试寻找第三个信标的位置。当且仅当存在一个整数坐标点，使得由两个幸存信标和该点构成的三角形面积等于 #cf_span[s] 时，系统才成功。此时，系统会向 aliens 发送一个包含信标位置的信息包；否则不发送。
请计算在 Mister B 移动信标的过程中，系统发送了多少个信息包。
第一行包含一个整数 #cf_span[t] (#cf_span[1 ≤ t ≤ 1000]) —— 测试用例的数量。接下来的 #cf_span[3·t] 行描述了 #cf_span[t] 个测试用例。
每个测试用例由三行描述。*注意：每个参数均以三个因子的乘积形式给出。*
测试用例的第一行包含三个空格分隔的整数：#cf_span[n1], #cf_span[n2], #cf_span[n3] (#cf_span[1 ≤ ni ≤ 106])，满足 #cf_span[n = n1·n2·n3]。
第二行包含三个空格分隔的整数：#cf_span[m1], #cf_span[m2], #cf_span[m3] (#cf_span[1 ≤ mi ≤ 106])，满足 #cf_span[m = m1·m2·m3]。
第三行包含三个空格分隔的整数：#cf_span[s1], #cf_span[s2], #cf_span[s3] (#cf_span[1 ≤ si ≤ 106])，满足 #cf_span[s = s1·s2·s3]。
*注意：仅允许对 #cf_span[t = 1] 的测试用例进行 hack。*
请为每个测试用例输出一个整数，每行一个。
## Input
第一行包含一个整数 #cf_span[t] (#cf_span[1 ≤ t ≤ 1000]) —— 测试用例的数量。接下来的 #cf_span[3·t] 行描述了 #cf_span[t] 个测试用例。每个测试用例由三行描述。*注意：每个参数均以三个因子的乘积形式给出。*
测试用例的第一行包含三个空格分隔的整数：#cf_span[n1], #cf_span[n2], #cf_span[n3] (#cf_span[1 ≤ ni ≤ 106])，满足 #cf_span[n = n1·n2·n3]。
第二行包含三个空格分隔的整数：#cf_span[m1], #cf_span[m2], #cf_span[m3] (#cf_span[1 ≤ mi ≤ 106])，满足 #cf_span[m = m1·m2·m3]。
第三行包含三个空格分隔的整数：#cf_span[s1], #cf_span[s2], #cf_span[s3] (#cf_span[1 ≤ si ≤ 106])，满足 #cf_span[s = s1·s2·s3]。
*注意：仅允许对 #cf_span[t = 1] 的测试用例进行 hack。*
## Output
请为每个测试用例输出一个整数，每行一个。
[samples]
## Note
第一个测试用例中，信标位置为：#cf_span[(2, 0)] 和 #cf_span[(0, 2)]，#cf_span[s = 3]。以下信息包可能被发送：#cf_span[((2, 0), (0, 2), ( - 1, 0))], #cf_span[((1, 0), (0, 2), (4, 0))], #cf_span[((0, 0), (0, 2), (3, 1))], #cf_span[((0, 0), (0, 1), ( - 6, 0))]，其中 #cf_span[(b1, b2, p)] 的含义为：#cf_span[b1] —— 第一个信标位置，#cf_span[b2] —— 第二个信标位置，#cf_span[p] —— 某个生成的点。
第二个测试用例中，信标初始位置为：#cf_span[(4, 0)] 和 #cf_span[(0, 5)]，#cf_span[s = 2]。以下信息包可能被发送：#cf_span[((4, 0), (0, 5), (0, 4))], #cf_span[((3, 0), (0, 5), (2, 3))], #cf_span[((2, 0), (0, 5), (2, 2))], #cf_span[((1, 0), (0, 5), (1, 4))], #cf_span[((0, 0), (0, 4), (0, - 1))], #cf_span[((0, 0), (0, 2), (2, 0))], #cf_span[((0, 0), (0, 1), (4, 0))]。
**Definitions**
Let $ t \in \mathbb{Z} $ be the number of test cases.
For each test case:
- Let $ m = m_1 \cdot m_2 \cdot m_3 $, $ n = n_1 \cdot n_2 \cdot n_3 $, $ s = s_1 \cdot s_2 \cdot s_3 $.
- Beacon 1 moves from $ (m, 0) $ to $ (0, 0) $ along the x-axis: its position at step $ i $ is $ (m - i, 0) $ for $ i = 0, 1, \dots, m $.
- Beacon 2 moves from $ (0, n) $ to $ (0, 0) $ along the y-axis: its position at step $ j $ is $ (0, n - j) $ for $ j = 0, 1, \dots, n $.
- The navigation system activates **simultaneously** when both beacons are at integer coordinates — i.e., at each time step $ (i, j) $, where $ i \in \{0, \dots, m\} $, $ j \in \{0, \dots, n\} $, the system checks for the existence of a point $ (x, y) \in \mathbb{Z}^2 $ such that the triangle formed by $ (m - i, 0) $, $ (0, n - j) $, and $ (x, y) $ has area exactly $ s $.
**Constraints**
1. $ 1 \le t \le 1000 $
2. $ 1 \le m_1, m_2, m_3, n_1, n_2, n_3, s_1, s_2, s_3 \le 10^6 $
3. $ m = m_1 m_2 m_3 $, $ n = n_1 n_2 n_3 $, $ s = s_1 s_2 s_3 $
**Objective**
For each test case, count the number of pairs $ (i, j) \in \{0, \dots, m\} \times \{0, \dots, n\} $ such that there exists $ (x, y) \in \mathbb{Z}^2 $ with:
$$
\frac{1}{2} \left| (m - i)(n - j) \right| = s
$$
That is, the area of the triangle with vertices $ (m - i, 0) $, $ (0, n - j) $, $ (0, 0) $ is $ s $, and since the third point can be chosen freely to adjust area (via vector cross product), the condition reduces to:
$$
|(m - i)(n - j)| = 2s
$$
Thus, count the number of integer pairs $ (i, j) $ satisfying:
$$
(m - i)(n - j) = \pm 2s
$$
with $ 0 \le i \le m $, $ 0 \le j \le n $.
**Final Objective (Formal)**
Compute:
$$
\left| \left\{ (i, j) \in \mathbb{Z}^2 \mid 0 \le i \le m,\ 0 \le j \le n,\ (m - i)(n - j) = 2s \text{ or } (m - i)(n - j) = -2s \right\} \right|
$$