Ntarsis 有一个盒子 $$$B$$$,边长为 $$$x$$$、$$$y$$$ 和 $$$z$$$。它位于 3D 坐标平面中,从 $$$(0,0,0)$$$ 延伸到 $$$(x,y,z)$$$。
Ntarsis 有一个秘密盒子$$$S$$$。他想要选择其尺寸,使所有边长均为正整数,并且 $$$S$$$ 的体积为 $$$k$$$。他可以将 $$$S$$$ 放置在 $$$B$$$ 中的某个位置,这样:
- $$$S$$$ 平行于所有轴。
- $$$S$$$ 的每个角都位于整数坐标上。
$$$S$$$ 很神奇,所以当放在 $$$B$$$ 内的整数位置时,它不会掉到地上。
在选择 $$$S$$$ 尺寸的所有可能方法中,确定他可以选择将其秘密盒子 $$$S$$$ 放置在 $$$B$$$ 内的不同位置的最大数量。一旦选择了边长,Ntarsis 就不会旋转 $$$S$$$。
输入
第一行由一个整数 $$$t$$$ 组成,即测试用例的数量 ($$$1 \leq t \leq 2000$$$)。测试用例的描述如下。
每个测试用例的第一行也是唯一一行包含四个整数 $$$x, y, z$$$ 和 $$$k$$$ ($$$1 \leq x, y, z \leq 2000$$$, $$$1 \leq k \leq x \cdot y \cdot z$$$)。
保证所有测试用例中所有 $$$x$$$ 的总和、所有 $$$y$$$ 的总和以及所有 $$$z$$$ 的总和不超过 $$$2000$$$。
请注意,$$$k$$$ 可能不适合标准 32 位整数数据类型。
输出
对于每个测试用例,将答案作为整数输出到新行。如果无法选择 $$$S$$$ 的尺寸使其适合 $$$B$$$,则输出 $$$0$$$。
示例
输入 #1
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
输出 #1
8 2 5 0 4 4 1030301
注意
对于第一个测试用例,最好选择边长为 $$$2$$$、$$$2$$$ 和 $$$2$$$ 的 $$$S$$$,其体积为 $$$2 \cdot 2 \cdot 2 = 8$$$。可以证明有 $$$8$$$ 方法可以将 $$$S$$$ 放入 $$$B$$$ 中。
对于 $$$S$$$ 的每种可能排列,具有最小 $$$x$$$、$$$y$$$ 和 $$$z$$$ 值的坐标为:
1. $$$(0, 0, 0)$$$
2. $$$(1, 0, 0)$$$
3. $$$(0, 1, 0)$$$
4. $$$(0, 0, 1)$$$
5. $$$(1, 0, 1)$$$
6. $$$(1, 1, 0)$$$
7. $$$(0, 1, 1)$$$
8. $$$(1, 1, 1)$$$
坐标为$$$(0, 0, 0)$$$的$$$S$$$的排列如下所示:
对于第二个测试用例,边长为 $$$2$$$、$$$3$$$ 和 $$$3$$$ 的 $$$S$$$ 是最佳的。