E. Секретный ящик
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Ntarsis есть ящик $$$B$$$ с длиной сторон $$$x$$$, $$$y$$$ и $$$z$$$. Он находится в трехмерной координатной плоскости, простираясь от $$$(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$$$.

Пример
Входные данные
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$$$.

Координаты с наименьшими значениями $$$x$$$, $$$y$$$ и $$$z$$$ для каждого возможного расположения $$$S$$$:

  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)$$$

Расположение $$$S$$$ с координатой $$$(0, 0, 0)$$$ изображено ниже:

Для второго примера оптимально выбрать $$$S$$$ с длиной сторон $$$2$$$, $$$3$$$ и $$$3$$$.