Сегодня на уроке информатики Шамилю стало скучно, и он решил порисовать на клетчатой бумаге. На первом шаге он закрасил какую-то клетку чёрным, а затем следовал алгоритму: если на предыдущем шаге клетки были закрашены черным цветом, то он закрашивает все соседние с ними по стороне клетки, которые ещё не закрашены, в белый, а иначе соседние раскрашивались в чёрный.

На картинке ниже изображён листок Шамиля после трёх шагов. Номер на каждой клетке – это шаг, на котором он появился.

Всего в задаче $$$10$$$ тестов (кроме тестов из условия). Каждый тест оценивается независимо от других в 10 баллов.