设 $w$ 为一个正整数。对于正整数 $a$ 和 $b$，定义函数 $f_w(a, b)$ 为满足以下条件的最大整数 $k \ge 0$：对于所有整数 $0 \le i \le k$，数 $a + w \cdot i^2$ 都能被 $b + i$ 整除。如果不存在这样的 $k$，则令 $f_w(a, b) = 0$。可以证明，对于所有 $i \ge 0$，$a + w \cdot i^2$ 不可能总是能被 $b + i$ 整除，即函数 $f_w(a, b)$ 是良定义的。

给定三个正整数 $w, m_a$ 和 $m_b$。求和 $\sum_{a=1}^{m_a} \sum_{b=1}^{m_b} f_w(a, b)$。

输入格式

每个测试点包含多个测试用例。第一行包含测试用例的数量 $t$ ($1 \le t \le 5$)。接下来是各测试用例的描述。

每个测试用例仅一行，包含三个正整数 $m_a, m_b, w$ ($1 \le m_a, m_b \le 10^{18}, 1 \le w \le 10^6$)。

输出格式

对于每个测试用例，输出一个整数，即问题的答案。

样例

样例输入 1

5
1 1 239
6 3 1
15 10 3
1000 100 11
25 1000 50

样例输出 1

5
6
19
1519
34