Ada and TicTacToe

Statement

Ada the Ladybug was playing 3D Tic-Tac-Toe against her good friend Velvet Mite Vinit. They were playing on 3x3x3 field. Sadly, Vinit had to go home earlier so the game was left unfinished. Ada wants to know who would win the match (if they both played optimaly). You also know that Ada started.

Input:

The first line contains a single integer 1 ≤ T ≤ 1000, number of test-cases.

Each test-case will contain 9 lines with three character each, representing the field ('.' for empty place, 'x' for move of Ada and 'o' for move of Vinit). You are assured that the game is unfinished and valid.

First three lines represent the top field, the next three lines represent middle field and the last three lines represent the bottom field.

There will be a blank line before each test-case.

Output:

For each test-case, print the name of winner (Ada or Vinit).

Example input:

7

..o
o.x
xox
x.x
...
x.o
...
o.o
.x.

.x.
...
..o
o.x
x..
..o
..x
...
...

o..
...
o.x
.x.
...
.x.
o.o
.xx
oox

..x
..x
.o.
..x
..x
xo.
o..
..o
...

...
..x
..x
.o.
..x
o..
...
...
x.o

...
..x
..o
...
...
xo.
ox.
...
.ox

o..
x..
...
oxx
..o
.ox
..o
.x.
.x.

Example output:

Vinit
Vinit
Ada
Vinit
Ada
Vinit
Vinit

Example input:

1

xox
x.o
oox
o.o
x.x
xxo
x.o
oxo
ox.

Example output:

Ada

Time and memory limit:

  • 1 second
  • 64MB

Problem source: SPOJ

s