Problem: Problem description.
Tic-tac-toe is the third most popular activity to kill a lazy afternoon in Ardenia.Arthum and Breece are not fans of this game, but their mother told them to play, so they sit at a 5 x 5 board. Both have a large pile of marbles: marbles of Arthum have an A written on them and that of Breece have a B. However, as they are both two years old, they have no concept of rounds. Instead, they just toss their marbles as quick as possible, so after a while each board field has either marble A or marble B. 
At that point, they would like to determine the winner, but counting is not their strong point, either. (They are two years old, remember?) Recall that the goal of tic-tac-toe is to have three own marbles in a row, i.e., lying at three consecutive fields horizontally, vertically or diagonally. If both Arthum and Breece have their three marbles in a row, or neither of them has it, we call it a draw. 

Input

The input contains several test cases. The first line of the input contains a positive integer  Z  , denoting the number of test cases.
 Then Z input instances follow, each conforming to the following format: 
The input instance describes marbles placed on the board in a single game. The instance consists of 5 rows and each of them consists of 5 letters:  A or B .

 

Output

You should output one line describing the outcome of the game, i.e., one of the three possible strings: A wins, B wins, or draw .

 

Constraints

Z ≤ 10^5

 

Example
Input:
2
AABBA
BAAAB
AAABA
ABAAB
BAAAB
AAAAA
AAAAA
BAAAA
ABAAA
AABAA

Output:
A wins
draw

Solution (in PYTHON):

Solution:
import sys;

aw=False;
bw=False;
def main():
	tc=int(raw_input().strip());
	for x in range(tc):
		global aw;
		global bw;
		aw=False;
		bw=False;
		board=[];
		for y in range(5):
			board.append(raw_input().strip());
		checkHorizontal(board);
		checkVertical(board);
		checkDiagonal(board);
		global aw;
		global bw;
		if aw and bw:
			print "draw";
		elif aw and not bw:
			print "A wins";
		elif bw and not aw:
			print "B wins";
		else:
			print "draw";

def checkHorizontal(b):
	global aw;
	global bw;
	sta="AAA";
	stb="BBB";
	for i in range(5):
		r=b[i];
		if r.find(sta)>=0:
			aw=True;
		elif r.find(stb)>=0:
			bw=True;

def checkVertical(b):
	global aw;
	global bw;
	if aw and bw:
		return 1;
	vb=[];
	for i in range(5):
		s="";
		for j in range(5):
			s=s+b[j][i];
		vb.append(s);
	sta="AAA";
	stb="BBB";
	for i in range(5):
		r=vb[i];
		if r.find(sta)>=0:
			aw=True;
		elif r.find(stb)>=0:
			bw=True;

def checkDiagonal(b):
	global aw;
	global bw;
	if aw and bw:
		return 1;
	sta="AAA";
	stb="BBB";
	st=b[0][0]+b[1][1]+b[2][2]+b[3][3]+b[4][4];
	if st.find(sta)>=0:
		aw=True;
	elif st.find(stb)>=0:
		bw=True;
	st=b[1][0]+b[2][1]+b[3][2]+b[4][3];
	if st.find(sta)>=0:
		aw=True;
	elif st.find(stb)>=0:
		bw=True;
	st=b[2][0]+b[3][1]+b[4][2];
	if st.find(sta)>=0:
		aw=True;
	elif st.find(stb)>=0:
		bw=True;
	st=b[0][1]+b[1][2]+b[2][3]+b[3][4];
	if st.find(sta)>=0:
		aw=True;
	elif st.find(stb)>=0:
		bw=True;
	st=b[0][2]+b[1][3]+b[2][4];
	if st.find(sta)>=0:
		aw=True;
	elif st.find(stb)>=0:
		bw=True;
	
	st=b[0][4]+b[1][3]+b[2][2]+b[3][1]+b[4][0];
	if st.find(sta)>=0:
		aw=True;
	elif st.find(stb)>=0:
		bw=True;
	st=b[0][3]+b[1][2]+b[2][1]+b[3][0];
	if st.find(sta)>=0:
		aw=True;
	elif st.find(stb)>=0:
		bw=True;
	st=b[0][2]+b[1][1]+b[2][0];
	if st.find(sta)>=0:
		aw=True;
	elif st.find(stb)>=0:
		bw=True;
	st=b[1][4]+b[2][3]+b[3][2]+b[4][1];
	if st.find(sta)>=0:
		aw=True;
	elif st.find(stb)>=0:
		bw=True;
	st=b[2][4]+b[3][3]+b[4][2];
	if st.find(sta)>=0:
		aw=True;
	elif st.find(stb)>=0:
		bw=True;
if __name__=="__main__":main();