У Карины есть массив из \(n\) чисел \(a_1, a_2, a_3, \dots, a_n\). Она очень любит перемножать числа, поэтому она решила, что красота пары чисел — это их произведение. А красота массива — это максимальная красота пары соседних элементов в массиве.
Например, для \(n = 4\), \(a=[3, 5, 7, 4]\) красота массива равняется \(\max\)(\(3 \cdot 5\), \(5 \cdot 7\), \(7 \cdot 4\)) = \(\max\)(\(15\), \(35\), \(28\)) = \(35\).
Карина очень хочет, чтобы ее массив был максимально красивым. Для того чтобы достигнуть своей цели, она может удалить из массива некоторые элементы (или не удалять ничего). После удаления в массиве должно остаться хотя бы два элемента.
К сожалению, Карина не успевает сделать все свои дела, поэтому она просит вас посчитать максимальную красоту массива, которую она может получить, удалив произвольное число элементов (возможно, ни одного).
Выходные данные
Выведите \(t\) чисел, каждое из которых является ответом на соответствующий набор — максимальной красотой массива, которую сможет получить Карина.
Примечание
В первом наборе входных данных примера для получения максимальной красоты нужно удалить \(2\)-й элемент.
Во втором и третьем наборах входных данных примера не нужно делать удалений для достижения максимальной красоты.
В четвертом наборе входных данных примера необходимо оставить только первый и последний элементы.