Шоткуб
В видеоигре Namco Bandai «Tales of Graces» есть мини-игра-головоломка под названием Shotcube. В этой игре у вас есть 9 кубиков, расположенных на 7-на-7 квадратной сетке. Ваша цель — переместить кубики так, чтобы они все оказались в 3-на-3 квадрате. В игре этот 3-на-3 квадрат должен находиться строго в центре сетки, но для этой задачи он может быть расположен в любом месте на сетке.
Единственный способ перемещать кубики — это "стрелять" в них снаружи сетки. Если кубик находится рядом с краем сетки, вы можете "стрелять" в него, чтобы толкнуть его по прямой линии. Он будет двигаться, пока не столкнется с другим кубиком, после чего остановится. Вы можете стрелять в кубик только в том случае, если на его пути есть другой кубик, который его остановит. Если вы стреляете в кубик в направлении, где сразу за ним находятся один или несколько кубиков, все эти кубики будут двигаться вместе, пока самый дальний кубик не столкнется с другим кубиком (после того, как пройдет как минимум одну клетку сетки), после чего все они остановятся.
Рассмотрим сетку ниже. Стрелки показывают три допустимых выстрела; другие выстрелы недопустимы, либо потому что нет кубика рядом с краем сетки, либо потому что нет кубика, который остановил бы движение стреляемых кубиков. Три сетки ниже показывают результат стрельбы по первой строке вправо, по первому столбцу вниз и по пятому столбцу вниз соответственно.
Рисунок 1: Иллюстрация допустимых выстрелов и их результатов.
Входные данные
Ввод начинается с строки, содержащей одно целое число T, 1 ≤ T ≤ 10000, обозначающее количество тестовых случаев. Каждый тестовый случай состоит из 7 строк, каждая из которых содержит 7 символов, представляющих 7-на-7 сетку. Каждый символ — это либо "." (точка), либо "X"; "." указывает, что эта клетка пуста, а "X" указывает, что в этой клетке находится кубик. Каждый тестовый случай гарантированно содержит ровно 9 кубиков. Каждая пара тестовых случаев разделена одной пустой строкой.
Выходные данные
Для каждого тестового случая выведите минимальное количество выстрелов, необходимых для того, чтобы расположить кубики в 3-на-3 квадрате в любом месте на сетке, следуя описанным выше правилам. Если это невозможно, выведите число "-1".