题目描述

有一类游戏由 25 盏灯排成一个 5×5 的方阵。
每一盏灯有一个开关，游戏玩家可以改变它的状态。
每一步，游戏玩家可以改变某一盏灯的开关状态；
改变一盏灯的状态后，其上下左右相邻的灯也要相应改变状态。

用字符 1 表示一盏亮着的灯，字符 0 表示一盏熄灭的灯。给定若干游戏的初始状态，请判断对于每一个游戏，是否恰好用 6 步就能使所有灯都亮起。

输入格式

第一行一个整数 n，表示共有 n 个游戏初始状态。
接下来输入 n 组数据，每组数据 5 行，每行 5 个字符，每个字符为 0 或 1，每组数据之间用一个空行分隔。

• 对于 30% 的数据，n ≤ 5
• 对于 100% 的数据，n ≤ 500

输出格式

输出一共 n 行，每行一个不大于 6 的整数，表示使所有灯都亮起所需的最少步数；
如果某一初始状态用 6 步以内无法使所有灯都亮起，则输出 -1。

时间限制

1 秒

输入样例

3
00111
01011
10001
11010
11100
11101
11101
11110
11111
11111
01111
11111
11111
11111
11111

输出样例

3
2
-1