#1440. 映射

存在映射 $f:\mathbb{Z_{+}}^3\rightarrow\mathbb{Z_{+}}$，满足 $f(i,j,k)=2i^2+2j^2+k^2+ij+2ik+2jk$。

你现在已经知道了正整数 $n,m,p,x$，你需要求出在 $i\le n$，$j\le m$，$k\le p$ 的限制条件下，$f(i,j,k)=x$ 有多少组不同的解 $(i,j,k)$。

$(i,j,k)$ 是三元有序对，也就是说对于两个三元有序对，只要 $i,j,k$ 中任意一个数不相同，那么就是两个不同的三元有序对。

第一行输入一个正整数 $t$，表示测试数据的组数。

对于每组数据，输入共一行，四个正整数 $n,m,p,x$。

保证所有测试数据的 $n,m,p,x$ 的总和分别不超过 $10^7$。

输出 $t$ 行，每行一个整数，第 $i$ 行表示第 $i$ 组数据中 $f(i,j,k)=x$ 有多少组不同的解 $(i,j,k)$。

样例输入

6
5 5 5 10
11 4 5 14
114 4514 1919 810
114 4514 191 9810
9876 543 321 4567890
1000000 1000000 1000000 4567890

样例输出

1
0
1
7
16
170

保证所有测试数据的 $n,m,p,x$ 的总和分别不超过 $10^7$。

对于第一组数据，可以发现只有当 $i=1,j=1,k=1$ 时，$f(i,j,k)=10$；

对于第二组数据，可以证明不存在 $i,j,k$ 使得 $f(i,j,k)=14$。

对于第三组数据，可以发现只有当 $i=9,j=9,k=9$ 时，$f(i,j,k)=810$。

对于第四组数据，仅存在如下 $7$ 组解满足 $f(i,j,k)=9810$：