У 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\), когда выбраны его длины сторон.
Выходные данные
Для каждого набора входных данных выведите ответ в виде целого числа на новой строке. Если нет способа выбрать размеры \(S\), чтобы он поместился в \(B\), выведите \(0\).
Примечание
Для первого примера оптимально выбрать \(S\) с длиной сторон \(2\), \(2\) и \(2\), что дает объем \(2 \cdot 2 \cdot 2 = 8\). Можно показать, что есть \(8\) способов поместить \(S\) внутри \(B\).
Координаты с наименьшими значениями \(x\), \(y\) и \(z\) для каждого возможного расположения \(S\):
- \((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\).
Примеры
| № | Входные данные | Выходные данные |
|
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
|
8
2
5
0
4
4
1030301
|