Вам задана доска размера \(n \times n\), где \(n\) нечетно (не кратно \(2\)). Изначально в каждой клетке доски расположена одна фигура.
За один ход вы можете выбрать ровно одну фигуру, расположенную в какой-либо клетке и передвинуть ее в одну из клеток, имеющую общую сторону или угол с текущей клеткой, то есть из клетки \((i, j)\) вы можете передвинуть фигуру в клетку:
- \((i - 1, j - 1)\);
- \((i - 1, j)\);
- \((i - 1, j + 1)\);
- \((i, j - 1)\);
- \((i, j + 1)\);
- \((i + 1, j - 1)\);
- \((i + 1, j)\);
- \((i + 1, j + 1)\);
Конечно же, вы не можете двигать фигуры в клетки за пределами доски. Допустимо, что после хода в одной клетке будет находиться несколько фигур.
Ваша задача — найти минимальное количество ходов, необходимое, чтобы собрать все фигуры в одной клетке (т.е. в \(n^2-1\) клетках должно быть расположено \(0\) фигур и в одной клетке должны быть расположены \(n^2\) фигур).
Вам нужно ответить на \(t\) независимых наборов тестовых данных.
Выходные данные
Для каждого набора тестовых данных выведите ответ — минимальное количество ходов, необходимое, чтобы собрать все фигуры в одной клетке.