Kurukshetra OPC 2013

TRIVIADOR

Triviador is a war between two Kings.

You are given a 3D matrix containing characters 'X' and 'O'.

'X' - The region is owned by King 1

'O' - The region is owned by King 2

A king can attack an enemy region at each step. When a king attacks a region, he conquers all the enemy regions connected to it(not just the immediate neighbours). Every region is connected to all the regions that share an edge or a corner with it. The kings get alternate chances to attack. King1 gets the chance to attack first. Assume both kings are intelligent and find who will conquer the whole territory at the end of the war. It can be proved that one of the Kings can win for sure if he is intelligent!

Input Specification:

The first line consists of an integer t, which denotes the number of test cases. For each test case the first line consists of three integers a, b, c denoting the dimentions of the territory (each cell is a region). Then the description of each cell follows. Every region contains a character ‘X’ if it is owned by king1 or ‘O’ otherwise.

The description of the axbxc 3D matrix is represented by 'a' bxc 2D matrixes.


Output Specification:

For each test case output the result in a single line ‘X’ if king1 wins or ‘O’ if king2 wins.

Input Constraints:

1<=t<=50

1<=a,b,c<=50

Sample Input:

3

2 3 5

OXOOO

OOXXX

XXXXO

                                <- empty line just for clarity.

XOXOO

XOOXO

OXXOX

1 1 6

OXOXXO

1 1 3

OOO

Sample Output:

X

O

O

Explanation:

Case 1: King 1 wins in his first move by attacking any enemy region.

Case 2: King 2 can win if he is intelligent.

Case 3: King 2 already won.

Try the 2D version of this problem : http://www.spoj.com/problems/TWOKINGS