题目内容

小塔集团总部有一间神秘的魔法阅读室，它四四方方的，三边长为x,y和z：在三维空间内，我们可以假定它占据了(0,0,0)到(x,y,z)的空间。有魔法的地方在于，这里面是不存在重力的！这样一来，阅读桌就可以漂浮在任何位置。

小塔集团的大家都非常的热爱阅读，特别是在魔法阅读室里！所以，为了搭配魔法阅读室，大家购买了一张魔法阅读桌：这个桌子的体积为k,边长可以为任何的正整数。你需要将魔法阅读桌放入魔法阅读室，使得阅读桌的各边平行于对应轴，并且每个角都位于整数坐标上。

在所有可能的边长选取情况下， 旋转桌子被视为一种方向，找到全部三种方向里摆放方式数量最多的那种情况的数量之和。例如下图中，在$3*1*2$的空间里有一边长为(2,1,1)的阅读桌，左右方向有4种摆放方式，而竖直方向只有3种摆放方式，故我们选组左右方向计入答案。

输入描述

每个测试文件均包含多个测试点。第一行输入一个整数$T$($1≤T≤1000$)代表测试数据组数，每组测试数据描述如下：

第一行输入四个整数$x,y,z$和$k$($1≤x,y,z≤1000，1≤k≤10^9$),分别代表魔法阅读室的三边长和魔法阅读桌的体积。

除此之外，保证所有的$x$之和，$y$之和以及所有的$z$之和均不超过$1000$。

输出描述

对于每一个测试点，在一行上输出一个整数，代表不同的摆放方式数量。如果无法将魔法阅读桌放入阅览室，那么输出$9$

样例1

输入

2
3 1 2 2
1 2 3 7

输出

4
0

说明

对于第一个测试点，已经在题目中加以解释。

对于第二个测试点，无法将魔法桌放入阅读室。