E. 秘密盒子

时间限制：1 秒
内存限制：256 兆字节

Ntarsis 有一个盒子 $B$，边长分别为 $x$、$y$ 和 $z$。它位于三维坐标空间中，从 $(0,0,0)$ 到 $(x,y,z)$。

Ntarsis 有一个秘密盒子 $S$。他希望选择 $S$ 的边长，使得所有边长均为正整数，且 $S$ 的体积为 $k$。他可以将 $S$ 放置在 $B$ 内部的某个位置，满足：

• $S$ 的所有边与坐标轴平行。
• $S$ 的每个角点位于整数坐标上。
• $S$ 具有魔法，因此当放置在 $B$ 内部的整数坐标位置上时，它不会掉落到地上（即完全在 $B$ 内部）。

在所有选择 $S$ 边长的方法中，确定 $S$ 可以放置在 $B$ 内部的不同位置的最大数量。Ntarsis 一旦选定边长，就不会旋转 $S$。

输入

第一行包含一个整数 $t$（$1 \le t \le 2000$）——测试用例的数量。

每个测试用例的第一行（也是唯一一行）包含四个整数 $x, y, z$ 和 $k$（$1 \le x, y, z \le 2000$，$1 \le k \le x \cdot y \cdot z$）。

保证所有测试用例的 $x$ 之和、$y$ 之和以及 $z$ 之和均不超过 $2000$。

注意 $k$ 可能无法用标准的 32 位整数类型存储。

输出

对于每个测试用例，输出一行一个整数——答案。如果无法选择 $S$ 的边长使其能放入 $B$ 中，输出 $0$。

示例

输入

7
3 3 3 8
3 3 3 18
5 1 1 1
2 2 2 7
3 4 2 12
4 3 1 6
1800 1800 1800 4913000000

输出

8
2
5
0
4
4
1030301

注释

在第一个测试用例中，最优选择是 $S$ 的边长为 $2, 2, 2$，体积为 $2 \cdot 2 \cdot 2 = 8$。可以证明有 $8$ 种将 $S$ 放置在 $B$ 内部的方法。

$S$ 的角点可以放置的最小坐标值（$x, y, z$ 方向上的起始位置）为： $(0,0,0)$、$(1,0,0)$、$(0,1,0)$、$(0,0,1)$、$(1,0,1)$、$(1,1,0)$、$(0,1,1)$、$(1,1,1)$。 当 $S$ 的角点位于 $(0,0,0)$ 时，其位置如下所示（示意图）。

在第二个测试用例中，最优选择是 $S$ 的边长为 $2, 3, 3$。