题目描述

你玩过“拉灯”游戏吗？ $25$ 盏灯排成一个 $5\times 5$ 的方形。每一个灯都有一个开关，游戏者可以改变它的状态。每一步，游戏者可以改变某一个灯的状态。游戏者改变一个灯的状态会产生连锁反应：和这个灯上下左右相邻的灯也要相应地改变其状态。

我们用数字 $1$ 表示一盏开着的灯，用数字 $0$ 表示关着的灯。下面这种状态：

在改变了最左上角的等的状态后将变成：

再改变它正中间的灯后状态将变成：

给定一些游戏的初始状态，编写程序判断游戏者是否可能在 $6$ 步以内使所有的灯都变亮。

输入格式

第一行有一个正整数 $n$ ，代表数据中共有 $n$ 个待解决的游戏初始状态。

以下若干行数据分为 $n$ 组，每组数据有 $5$ 行，每行 $5$ 个字符。每组数据描述了一个游戏的初始状态。各组数据间用一个空行分隔。

输出数据一共有 $n$ 行，每行有一个小于等于 $6$ 的整数，它表示对于输入数据中对应的游戏状态最少需要几步才能使所有灯变亮。

对于某一个游戏初始状态，若 $6$ 步以内无法使所有灯变亮，请输出 -1。

3
2
-1

对于 $30\%$ 的数据， $n\le 5$ 。

对于 $100\%$ 的数据， $n \le 500$ 。