Mister B and Beacons on Field
Contest: Codeforces Round 421 (Div. 1)
Difficulty rating: 2900
Tags: number theory

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 format:
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: n1, n2, n3 (1 ≤ ni ≤ 106) such that n = n1·n2·n3.

The second line contains three space-separated integers: m1, m2, m3 (1 ≤ mi ≤ 106) such that m = m1·m2·m3.

The third line contains three space-separated integers: s1, s2, s3 (1 ≤ si ≤ 106) such that s = s1·s2·s3.

Note that for hacks only tests with t = 1 allowed.

Output format:
Print t integers one per line — the answers for each test.

Constraints:
Time limit: 5.0 s
Memory limit: 256.0 MB

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 (b1, b2, p) has next description: b1 — first beacon position, b2 — 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)).

Example input:
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

Example output:
4
7
171

Editorial:
There 2 stages in this task: moving of first beacon and moving of second.
But at first we need factorization of n and s. Since n and s are product of integers  ≤ 106, it can be done in O(log(n) + log(s)) time by "Sieve of Eratosthenes".
Start from second stage, when second beacon is moving:
Position of beacons will look like pair of points: (0, 0), (0, k), where 0 ≤ k ≤ n.
We need to check existing of point (x, y) such, that area of triangle (0, 0), (0, k), (x, y) equals to s. Using cross product |((0, k) - (0, 0))·((x, y) - (0, 0))| = 2·s. After simplifying we get |k·x| = 2·s where 0 ≤ k ≤ n.
So we can iterate all divisors of 2·s, using factorization of s and recursive algorithm.
Complexity of second stage is O(σ (s)), where σ (s) — number of divisors of s and for s ≤ 1018 σ (s) ≤  ≈ 105.
In the first stage we have such points: (k, 0), (0, n), where 1 ≤ k ≤ m.
We need to check existing of point (x, y) such, that area of triangle (k, 0), (0, n), (x, y) equals to s. Using cross product |((k, 0) - (0, n))·((x, y) - (0, n))| = 2·s we can get next equation: |k·(y - n) + n·x| = 2·s. Then solution exists iff gcd(k, n) | 2·s (2s % gcd(k, n) = 0).
And we need to calculate how many 1 ≤ k ≤ m such, that gcd(k, n) | 2·s.
We will solve it in next way: let's n = p1n1p2n2... plnl and 2s = p1s1p2s2... plsl (ni, si ≥ 0).
Look at all pi, that ni > si. It's obvious, that if pisi + 1 is divisor of k, then 2s doesn't divide at gcd(k, n).
In result, we have some constrains on k, like k doesn't divide at aj = pijsij + 1.
Finally, we have next task: calculate number of k (1 ≤ k ≤ n) such, that k doesn't divide any of ai. It can be done with inclusion-exclusion principle, where number of k which divides ai1, ai2 ... aib is $$\frac{n}{a_{i_1}a_{i_2}\ldots a_{i_b}}$$.
Complexity of first stage is O(2z(n)), where z(x) — number of prime divisors of x, z ≤ 15 for integers up to 1018.
Result complexity is O(σ (s) + 2z(n)) per test.