Description
Gomoku(Five in a Row) is a two-player board game. Two players(black and white) take turns placing a stone of their color on an empty intersection. The first player who forms an unbroken chain of 5 or more stones(horizontally, vertically, or diagonally) is the winner.
You have to solve q tasks. In each task, you need to output the winner(there may be no winner) for the given Gomoku board.
And in this problem:
- gridsize of the board is considered 15 x 15
- black is always the first player who starts placing the stone
- the given board must be valid
- don't consider any variation of the rule(like renju, Swap2...)
Here are three illustrations about the sample.
 |
 |
 |
| the board given in the first task | the board given in the second task | the board given in the third task |
The content of the sample is so many. So it's not recommended to type the sample manually to test your code.
Input
The first line contains an integer q (1 ≤ q ≤ 100) – the number of tasks you have to solve.
For each task, there are exactly 15 lines which contain exactly 15 characters each – the board you are given. 'b' and 'w' represent the stone placed by black and white respectively. And '.' represents an empty intersection.
Output
For each task output the winner(output "none" if there is no winner).
Remember to print a newline('\n') at the end of each line(task).