C. Mister B and Beacons on Field

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]。 *注意：仅允许在 hacks 中使用 #cf_span[t = 1] 的测试。* 请为每个测试用例输出一个整数，每行一个。 第一个测试用例的信标位置为：#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))]。 ## 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]。*注意：仅允许在 hacks 中使用 #cf_span[t = 1] 的测试。 ## 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 $ n = n_1 n_2 n_3 $, $ m = m_1 m_2 m_3 $, $ s = s_1 s_2 s_3 $, where $ n_i, m_i, s_i \in \mathbb{Z}^+ $. - Let $ A = (m, 0) $, $ B = (0, n) $ be the initial positions of the two surviving beacons. - Let $ P = (x, y) \in \mathbb{Z}^2 $ be a candidate point for the third beacon. **Constraints** 1. $ 1 \le t \le 1000 $ 2. $ 1 \le n, m, s \le 10^{18} $ (since each is a product of three integers $ \le 10^6 $) 3. During movement: - The first beacon moves linearly from $ (m, 0) $ to $ (0, 0) $, passing through all integer points $ (m - k, 0) $ for $ k = 0, 1, \dots, m $. - The second beacon moves linearly from $ (0, n) $ to $ (0, 0) $, passing through all integer points $ (0, n - \ell) $ for $ \ell = 0, 1, \dots, n $. - At each time step, the two beacons are at positions $ (a, 0) $ and $ (0, b) $, where $ a \in \{0, 1, \dots, m\} $, $ b \in \{0, 1, \dots, n\} $, and the system activates **only when both are at integer coordinates** (which is always true during movement). **Objective** Count the number of distinct pairs $ (a, b) \in \{0, 1, \dots, m\} \times \{0, 1, \dots, n\} $ for which there exists at least one point $ P = (x, y) \in \mathbb{Z}^2 $ such that the area of triangle $ \triangle APB $ equals $ s $. The area of triangle with vertices at $ (a, 0) $, $ (0, b) $, and $ (x, y) $ is: $$ \text{Area} = \frac{1}{2} \left| a b - a y - b x \right| $$ We require: $$ \frac{1}{2} \left| ab - ay - bx \right| = s \quad \Rightarrow \quad \left| ab - ay - bx \right| = 2s $$ This equation has an integer solution $ (x, y) \in \mathbb{Z}^2 $ **if and only if** $ \gcd(a, b) \mid 2s $. Thus, for each $ (a, b) \in \{0, \dots, m\} \times \{0, \dots, n\} $, count 1 if $ \gcd(a, b) \mid 2s $, else 0. **Final Objective** Compute: $$ \sum_{a=0}^{m} \sum_{b=0}^{n} \mathbf{1}_{\gcd(a,b) \mid 2s} $$ (Note: $ \gcd(0,0) $ is undefined, but when $ a = b = 0 $, the triangle degenerates; area is 0, so only valid if $ s = 0 $. Since $ s \ge 1 $, we exclude $ (0,0) $ or treat $ \gcd(0,0) $ as 0, and $ 0 \nmid 2s $, so it contributes 0.) Thus, the answer for each test case is: $$ \sum_{\substack{a=0 \\ b=0 \\ (a,b) \ne (0,0)}}^{m,n} \left[ \gcd(a,b) \mid 2s \right] $$ But since $ \gcd(0, b) = b $ for $ b > 0 $, and $ \gcd(a, 0) = a $ for $ a > 0 $, we can include $ (0,0) $ with $ \gcd(0,0) = 0 $, and since $ 0 \nmid 2s $, it contributes 0. So we may safely write: $$ \sum_{a=0}^{m} \sum_{b=0}^{n} \left[ \gcd(a,b) \mid 2s \right] $$ with the convention that $ \gcd(0,0) = 0 $, and $ 0 \nmid k $ for $ k \ne 0 $.