Алиса очень любит бросать камни в море и наблюдать, как красиво вокруг них распространяются волны. Девочка настолько очарована этим процессом, что решила запечатлеть процесс распространения волн на своих рисунках.

Представим море как бесконечное поле, состоящее из клеток. На рисунках ниже клетка, в которую был брошен камень, обозначена буквой «К». Брошенный в воду камень, разумеется, создает вокруг себя волны: ровно через одну секунду после того, как камень был брошен, в четырех соседних по стороне клетках образуются волны. На рисунках ниже клетки, в которых образовались волны, обозначены черным цветом.

На этом распространение волн не заканчивается. Каждую секунду рисунок волн изменяется следующим образом: каждая черная клетка становится белой, а ее четыре соседние по стороне клетки становятся черными. На втором рисунке ниже изображена картина волн спустя две секунды после броска камня.

Рисунок 1. Распространение волн

Процесс распространения волн продолжается бесконечно, и это очень радует Алису. Рисунок моря спустя $$$T$$$ после броска камня представить в своем воображении достаточно сложно. А вот посчитать количеств волн, изображенных черными клетками на рисунке через $$$T$$$ секунд после бросания камня, достаточно легко — так считает Алиса. Убедитесь в этом и вы.

Помимо тестов из условия данная задача содержит $$$25$$$ тестов, каждый из которых оценивается независимо в $$$4$$$ балла.