Известный в Берляндии художник Калевич любит эпатировать общественность. Его последняя идея фикс — шахматы. Вот уже более тысячи лет люди играют в эту древнюю игру на неинтересных, однообразных досках. Калевич решил разрушить эту традицию, представив новый взгляд на шахматные доски.

Как и прежде, шахматная доска это квадратное поле 8 × 8 клеток, каждая из которых покрашена в черный или белый цвет. Калевич предлагает красить шахматные доски, выбирая на поле горизонтальный или вертикальный ряд из 8-ми клеток (т.е. строку или столбец) и закрашивая его в черный цвет. Изначально вся доска белая, а такие покраски можно делать один или более раз. Многократная покраска клетки допустима, но после первой покраски цвет клетки не меняется и остается черным. Калевич красит доски очень аккуратно и по любой отдельно взятой клетке невозможно понять, была она покрашена вертикальным или горизонтальным мазком.

Калевич надеется, что такие доски станут популярны, и ему будут поступать заказы на покраску досок, обеспечив его безбедную старость. Клиенты будут предоставлять ему информацию о том, какую доску они хотят иметь, а художник будет красить белую доску, реализуя идею клиента.

Конечно, в таком бизнесе надо экономить на всем — для каждого заказа Калевич хочет знать наименьшее количество мазков, которое ему надо совершить, чтобы выполнить требование клиента. Помогите Калевичу с этой несложной задачей.