SPOJ.com - Problem EYES

EYES - Robo Eye

A robot which helps to translate old papers into digital format is being prepared for mass production. But it requires special software to work efficiently. All scans which will be analyzed by the robot use one of the standard fonts: Arial, Courier, or Times New Roman. As the press is not ideal and pages can be rotated, some of the scans will be rotated by some degree. Imperfections of the robot's camera ("eye") can also cause some noise. Uniform noise can be up to 2% of the number of pixels. All analyzed documents are in uppercase English. The total number of letters in the robot's eye ranges from 3 to 6. The matrix in the robot's eye is monochrome and its size is 200x200 pixels.

Input

t – the number of tests [t <= 500], then t tests follows. Each test consists of 200 rows with 200 chars in each of them. Characters can be '.' and 'X', where '.' means the white color of the page, and 'X' is the black color of words.

The input data was generated using an on-line generator. The generator outputs data in 2 formats:

1) as a picture
2) as text

The datasets used for testing are such that all letters of the word are contained inside the picture.

Output

For each test output the recognized word in a separate line.

Score

The number of points you’ll receive for each image will be equal to the number of letters of the word, provided that it is correctly recognized.

Example

Input: 2

...........X...........X..............................................................X................................................................................................................. .............................................X...........................X......................X.........................................X...............................................X............. ........................................................................................X............................................................................................................... X............X....X...............................................................................................................X......X..................X......X.......................X..X......... .........................................................X.........X.............................X.........................X.....XXX........X................................X.......................... ................X.................................X...X....X......X.........................X...................................XXXXX.........................X......................................... ..............................X.X...........X.......................................................X......X....X.........X....XXXXXXX.........................................X........X............... ..............................................X...................................................................X..X.........XXXXXXXX................................................................. ......................................................................................................................X..........XXXXXXX................................................................ .....................................................................X............................................................XXXXXXX.......X......................X................................ ...................................................X...........................X.....X...........X........X........................XXXXXXX...........................X.................................. .......................X...............................................................X............................................XXXXXXX.......................X...X................................. .........X.................................................................................................X......X..................XXXXXXX.......................................................X.... .............X.........X.............................................X.....X...X.............X........................................XXXXXXXX...........................X...............X.............. ...X....................................X.........................................................................................X....XXXXXXXX......................................................... ......................................X..........X...................................................................................X..XXXXXXXX.......................X................................ ...........................................................................X.............................................................XXXXXXXX....................................................... .....................................................X..X.........................................X.................XX...........X........XXXXXXXX......X.....................................X......... ......................X............................................................................................XXXXXXX.................XXXXXXXX....XX.................X............................. ....................X...........................................................................X..............X..XXXXXXXXXXXXX.............XXXXXXXX......X.....................X....................... ................................................................X................................................XXXXXXXXXXXXXXXXXXX.........XXXXXXXX...............X................................... .............................................................................X......X..............X..............XXXXXXXXXXXXXXXXXXXXXXX.....XXXXXXXX..........X.......................X............... ......................X...........X.............X.............X....................................................XXXXXXXXXXXXXXXXXXXXXXXXXX..XXXXXXXX..............................................X.. ....................................................................................................................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX....................................X........... .X...................X.............................................................X.................................XXXXXXX...XXXXXXXXXXXXXXXXXXXXXXXXXX..X.........................................X.. ................................X..................................................................................X..XXXXXXX.......XXXXXXXXXXXXXXXXXXXXXX...........X.................................. ..................................X..............................................................................X.....XXXXXXX...........XXXXXXXXXXXXXXXXX...........................................X.. .......................................X................................................................................XXXXXXX..............XXXXXXXXXXXX............................................... .....XX...........................................................................X......................................XXXXXXX..................XXXXXX................................................ ..............................................................................................................X...........XXXXXXX..................................................X.................... ................X.....................................X.......................................X............................XXXXXXX.X.........X.............X......................X..............X...... ......................................................................................................X.....................XXXXXXX.................................X.............................X...X. ....................X..X..................................................X...........................X......................XXXXXXX...............X.....X............................X................. ..................................................X....X.......................................................X..............XXXXXXX................................................................... ...........................X.............................................................X.X...................................XXXXXXX.................................................................. ........X.X.......X..........................................................................X......................X...........XXXXXXXX..............................X................................. .X............................................................................X...................XXX............................XXXXXXXX.........................................X..................... ........X..................................X.....................................................XXXXX............................XXXXXXXX........................................X.................X... ................................................................................................XXXXXXX........X...................XXXXXXXX............................................................. .................................X.......................X.......................................XXXXXXX............................XXXXXXXX..X....X...............X.................................... ................................................................X.................................XXXXXXX............................XXXXXXX..............X.................................X........... ...................................................................................................XXXXXXX....................X.......XXXXX.....................X....................................... ......X........................................X....................................................XXXXXXX............................XXX.............................................................. ................X....................................................................................XXXXXXX............X...............X.....................................................X......... ......................................X...................................................XXX...X.....XXXXXXX....................XX....................................................................X ......................................................X..................................XXXXX.........XXXXXXX..................XXXX.....................X..X........................................... ...................................X........................X...........................XXXXXXX.........XXXXXXX.XX..............XXXXX................................................................... .........................................................................................XXXXXXX.X.......XXXXXXX...............XXXXXX....................X.............X................................ .................................................................................X.....X..XXXXXXX.........XXXXXXX.....X.......XXXXXXX................................................................X.. .......................................X...................................................XXXXXXX.........XXXXXXX...........XXXXXXX........X.............X............................X................ .....................................................X...X..................................XXXXXXX.........XXXXXXX.........XXXXXXX............................................X........................ ...........................................X.....................X.........................X.XXXXXXX.X.......XXXXXXXX.X....XXXXXXX...........................................X.......................... ..........X...........................................................X............X..........XXXXXXX.........XXXXXXX.....XXXXXXX.....X.............X............................X...X.................. .X.................................................................X..............XXX..........XXXXXXX.........XXXXXXXX..XXXXXXX..X.................X................................................... ...................................X.............................................XXXXX..........XXXXXXX........XXXXXXXXXXXXXXXX............................................X............................ ................................................................................XXXXXXX..........XXXXXXX.........XXXXXXXXXXXXX.......X......................................X........................... ...................................X.....X......X................................XXXXXXX..........XXXXXXX.........XXXXXXXXXXX..............................................................X............ .......................................X..........................................XXXXXXX..........XXXXXXX......X..XXXXXXXXX...................X...........................X.......X.................... .......................................................................XX..........XXXXXXX...X..X...XXXXXXX..X......XXXXXXX.....................X................X.....................X................ .........................X........................X.................................XXXXXXX..........XXXXXXX.........XXXXX...................X..............................................X........... ................................X..X..X..............................................XXXXXXX..........XXXXXXX.X.......XXX......X.......................................................X................ .......................................................X..............................XXXXXXX..........XXXXXXXX........X...........................X.................................................... .................................................................X.....................XXXXXXXX.........XXXXXXXX.................................................................X...................... .......................X................................................................XXXXXXXX.........XXXXXXXX.............................................X......................................... ...................................X.X.................X..............X..................XXXXXXXX.........XXXXXXXX....X..X...........................................................X.................. ..........................X....................X........X.................................XXXXXXXX.........XXXXXXXX.................................X..X.......X........................................ .X........................................X..........................XX........X...........XXXXXXXX.........XXXXXXX........................X................................................X........... ....................................................................XXXXXXX....X............XXXXXXXX.........XXXXX.....X........................X....................................................... .....................................X................X...........XXXXXXXXXXXXXX.............XXXXXXXX.......X.XXX....................................................................................... X........................X........................................XXXXXXXXXXXXXXXXXXX.........XXXXXXXX.........X......................................X................................................. .................X.................................................XXXXXXXXXXXXXXXXXXXXXXX.....XXXXXXXX.............X........................................................................X.......... ......X....................X...................................X....XXXXXXXXXXXXXXXXXXXXXXXXXX..XXXXXXXX...............................X........................................................X.X..... .............................X...X...................................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX........................................X...................................................... .....................................X........................XX......XXXXXXX...XXXXXXXXXXXXXXXXXXXXXXXXXX..........................X................................................................... .............................................................XXXX......XXXXXXX.......XXXXXXXXXXXXXXXXXXXXXX..........................................................................................X.. .....X..........................................X...........XXXXXX......XXXXXXX...........XXXXXXXXXXXXXXXXX...........XX...X............................................................................ ................X...........................................XXXXXX.......XXXXXXX..............XXXXXXXXXXXX.....X........................................................................................ ...........................................X.................XXXXXX.......XXXXXXX..................XXXXXX............................X.....................................X............................ .......X.................................X....................XXXXX........XXXXXXX...................................................X.............................X.................................... ..............................................................XXXXXX........XXXXXXX..X..........X.........................X.....................................X...............X...............X....... .............X............................................X....XXXXXX....X...XXXXXXX........X...........................................................X.........X...................X........X........ .....................................................X..........XXXXX.........XXXXXXX.................XX................................................................................................ ..........X.....................................................XXXXXX.........XXXXXXX........................................................................X......................................... ...........................................X.....................XXXXXX.........XXXXXXX................................................................................................................. .................................................................XXXXXX..........XXXXXXXX...................X..X........X............................................................................... ...............................X...........................X......XXXXXXX.......X.XXXXXXXX...........X................X..................X..................X........................................... .........................X........................XX...............XXXXX...........XXXXXXXX................................X.................X.........X................................................ .................................................XXXXX.X...........XXXXXX...........XXXXXXXX...................................X........................................................................ X........................................XX..X..XXXXXXXX............XXXXXX...........XXXXXXXX.....................X.........................................................................X........... ...............................................XXXXXXXXXXX...........XXXXX.X..........XXXXXXX...................X..........X...............................................X............................ ....X.........................................XXXXXXXXXXXXXX.........XXXXXX............XXXXX.....................................................X.....................X............X....X.............. ......X.......................................XXXXXXXXXXXXXXX.........XXXXX.............XXX...........................X................................................................................. ........................X......................XXXXXXXXXXXXXXXX........XXXXX.............X...................................................................................................X.....X.... ...............................................XXXXXX.XXXXXXXXXXX......XXXXXXX..................................................X....................................................................... .........................X......................XXXXXX.XXXXXXXXXXXX.....XXXXX.....................X..............................X...........................X.......................................... ................................X................XXXXX....XXXXXXXXXXX....XXXXX..........................X....................................X.......X...X.......................................X...... ............X......................X.............XXXXXX.....XXXXXXXXXXX..XXXXX..................................................................................X....................................X.. ........................X.........................XXXXXX......XXXXXXXXXXX.XXXXX...............X...........................................................................X............................. ..................X...........X...................XXXXXXX.......XXXXXXXXXXXXXXXX........................................................................................................................ ..............................................X...XXXXXXX.........XXXXXXXXXXXXXX.........................................................X............................X................................. ...................................................XXXXXX...........XXXXXXXXXXXXX..................................X.................................................................................... ...................................XXX..............XXXXXX............XXXXXXXXXXX....................................................................................................................... ..................................XXXXXX.............XXXXX..............XXXXXXXX........................................................................................................................ ............X...X................XXXXXXXXX...........XXXXXX..............XXXXXXX.......................................X................................................................................ .....X...........................XXXXXXXXXX...........XXXXXX...............XXXX....................X...................X..............................................X..X.............................. ...................................XXXXXXXXXX.......X.XXXXXX...........................................................X.........................................................X....................X. .....................................XXXXXXXXXX........XXXXXXX....................................................................X...........................................X......................... .......................................XXXXXXXXX.....X.XXXXXX.....................................................................................................................X..................... ..X.....................................XXXXXXXXXX......XXXXXX.......................................................................................................................................... ...................................X....X.XXXXXXXXXX.....XXXXX................X......................................................................................................................... ...............................X......X.....XXXXXXXXX....XXXXXX.............XX..............................................................................................X...................X....... ..............................................XXXXXXXXX...XXXXXX.....................X.................................................................................................................. ................................................XXXXXXXXX.XXXXXX...X............................X.................................X...........X..X...................................................... X......X.X........................X.X............XXXXXXXXX.XXXXXX.........................X................X.....X.....................................................X...................X............ ...................................................XXXXXXXXXXXXXX....................................X.....................X............................................................................ .................................XX..................XXXXXXXXXXXXX...........................................X...X.X..........................................................................X......... ...........................X...........................XXXXXXXXXXX...X......................................X..................X........................................X............................... ...............................................X.........XXXXXXXXX.....................X................................................................................................................ ..........................................................XXXXXXX..............................................................X.....................................X.................................. .............................X..........................X...XXXX...........X............................................................................................................................ ....X..X..................................................X...X......................................X.....................X.....................................X...................................... ....X....................................................X..............................X......X........................................................................................................ ........................................................................................................................................................................................................ ........................................X......X..X...............X...........................................................................X.......................X.............X................... ......................X......................................................X.....X...............X.................................................................................................... .........X.................................................................................................................X..........X..................................................X.............X ...........................X......................................................................................................................................X.....X............................... ......................................X...........................................................................X.......................................................X.........X.................X. .............................................................................................................................................................................X....................X..... ....................................................................X................................X.................................................................................................. .................................................................................X.............................................X........................X......................X........................ ........................X..................................................................................X...........................................................................X................ ...........X.......................................X................X..............................X........................................................X.................................X......... ..........X.....................................................................................................X....................................................................................... ........................................................................................................................................................................................................ ................................................................................................................X...............................................................X....................... .............................X..............................................................X....................................................................X...................................... .....................X...............X....................X..................X....X.......X...............................................X......X...................................................... ......................................................................................................................................................................X........................X........ ..............................X.....X..................................................................................................................X..........X....................X..............X. ...........................X.X......................X.........X...............................X.......X..................................X................................X............................. ..X............................................................................X..........X......................................X....................................................X................. .........................................................................................................................................................................X..........X..X................ .......................................................................................................................................X..........................X..........................X.........X .....X.................................................X...........................X......X.................................................................................X........................... ............................X............................................................................X.X........................X...X.........................................................X..... ..X...........................................................X.......X...................................................X......................................................................X...... ...........................X......................X....................X........................................................X.....X................................................................. ...................................X.................................................................................................................................................................... ....................................................X.......................................................................................................X.......X.....................X.X........... ..........................XX.......................................................X...................X.......................................................................X........................ .................................X....................................................X.........................................................................X............................X.....X.... .................................................................X.......................................................X.............................................................................. ............X...................X...................................................................................X..........................X........................................................ ..............X......................................................................................................................................................................................... ........................................................................................X............................................................................................................... ..............................................................................X..................X.............................X........................................................................ .........................................................................X....X.............................X.....................X..................................................................... ..............................X............................................................X...................................X.................................................................X...... ..........................................................................................................X.......X..................................................................................... .............................................................................................X.....X.................................................................................................... ..X............................................X...............................................................................X........................................................................ ..................................................X...................X............................................X..X......................X...X..................X................................... ...........X.......................................X.X.......................................X................................................................................X................X........ ................................................X..................................................................X...............................X.................................X.................. ..X....................................................................X.................................................................................................................X.............. .....................................X..............................................................................................X................................................................... ......X........................................X..........................................................................................X.........................................................X... ..................................................X...................X..............................................................................................X........X......................... .............X....................................................................X.......................X..................................................................X.......................... .............................X................................................................X....................................................X...............................X.......X............ .................................X..................................................................................X........................X.........X....................X...................X....... .................................................................................................X.........................X............................................................................ ...........X...X..............................................................................X......................................................................................................... ..................................................................................................................................X..................................................................X.. ......X.........................................................................................................................X....................................................................... .......................................................................................................................X................................X..............................................X ......................................................X..................................X...............................X.............................................................................. .............................X................................................................X.......................................................................XX.................X.............. .........................................X..........X.....................................................................................X.................X...X......................................X ......................................................X..........................................................................................................XX.....X............................... .X..........................X...................X.....................................................X...................................................................X............................. .............................................................X.................................................................................X..........................................X........X.... ..........................................X............................................X................................................................................................................ ......X..........X........................................................................................................X......X............................................................X......... ...................X...............X.............................................................................X........................................................X...X......................... ....................................X...........X..................................X.................................................................................................................... .............X........................................................X........X.......................................................X................................................................ ..................X............................................X.........................................X............................................X................................................X ........................................................................................................X..X...........................................................................................X .........................................X...................................................................................................................................................X.......... .......................X.......................................................................X....X................................................................................................... ...............................................................................................X.....................................X.................................................................. ....X...........................................X...............................................................X.............X..............X.......................................................... ....................................................X..............................................................................................X..X......................X....................X..... ............................................................................................X...............................X...............................X................X..........X............... ...X.............X...............X...........X.....................................................................................................................X.................................... .................................................................................................................................................X........................XX.X.......................... .X......X.............................X..............X.........................................................X................X.....X................................................................. ...X..............................................X..................................................................................................................................................... ..............X................................................................X....X................................................................................................................... .........................X...............................................................X..X........................................................................................................... .......................X................X..........X....................X.................................................X.....................X................X...................................... ......................X...........................................................................................X.......................................X.........X................................... ...........X.........................................................................................................X...........X..........................X........................................... ................................X.............X...X.........................................X...............X........................................................X...............X.................. .................................................................X..............X.........X..............X..........................................X...................X............X.................. ....................................................................................X................................................................X...................X.............................. ..X...................................................................................................................................................................X.....X........................... ............................................................................X...........................X............................................................................................... .........................................................................................................................X................................X............................................. ...................................................X.....................................................X......................X....................................................................... ...................................X...............................................X............X....................................................................................................... ....................................................X..........X..................................X......X....................................................X................................X........ ............................X.......................................X..........................X.............................................X........................................X.........X....... ....................................................................................................................................................................................................X... ....................................X....................................................X.X...................X...X...............................................................X.................... ...................X.......................................................................X............................................................................................................ ..................................X............X.............................................................................X.......................................................................... ............X..................X...........................................X...X..........X.............................X........X.......................X...........X.........X..............X......... ................................................................................................................X...............................X......X...X..............................X............. ......................................X...............................................................................................................X.X...................................X........... X.............................................X..........X........................................................................................X................X.................................... .............................................................................X.......................................................................................................................... ............................................................X..............................X......................................X..................................................................... ..........................................................................................................................X............................................X................................ ...........................X..............................X...............................................................................X............................................................. .............................................X....................................................................X..................................................................................... ......................................................................................................................................................X...X............................................. ...........................................................................................X.................................................................................................X.X........ ..............................X.......................................................................X..X.............X..........X..............X...................................................... ..........................................................X....................................X......................................................X................................................. ..............X....................................................................................................X.............X...................................................................... .............................................XX.....X.....................................X............................................................................................................. ........................X................................X.X.......................................................................................................................................X.... ............X................X...............X............................................................................................X............................................................. X.....X...............................................................................................X................................................................................................. ........................................X.............................................................X..............X.............................................X.................................X.. ...................X...X..................................................X...................................X..............................................X...............................X.......... ....................................X.............................X..................................................................X...........................................................X...... ................................................X...............................X............X.................................................................................................X........ .......X..................................X............................................................................................................................................................. .................X.............X....X............................................................................................................................X............X......................... ...........................................................X............................................................................................................................................ ............................................................................................X...........X.......X.........................X..................................X.........................X ...X....................................................................................X..............X..X............................X................................................................ ....................................................X...........................X............X...................................................................X.X.................................... ....................................X..........X......X...........................................X..........X.........X.........X.................................................................X.... ...............................................X...........X.X....................................................X...............X..................................................................... ...................................................................X.................................................................................................................................... ...........................................................................................................................................................................X...X........................ ...............................................X........................................X..............................................................................................X................ ....................................X..............................X.........X.X........................................................................X............................................... ........................................................X....X........................................................................X....................................X.........................X.. ....................X........................................................................X.............................................X..X...............X..X...................................... .........................X..................................X...............................X...X.............................................................X......................................... ...............X.......................X....................X......X....................................................................................X...........................................X... ............................................X...........X...............X..................X...........X....................................X........................................................... ...X.....................................................X.............................................................................................................................................. .....................................................X..................................X...................................................................................X........................... ........X.............................................................X................X.....................................X.......................................X.................................. X..................X......X...........................................................................................X...............X................................................................. .........................................................................X.......................................................................................................X..............X....... ..............X..........................X...........................X..............................X................................................................................................... ..................................X.............X..................................................................................................X...................................................X ....................................X................................................................................................................................................X....X............. .............X.......................................................................................................................................................................................... .................................X..................................................................................................................................................X.................X. ....................................................................................X................................................................................................................... .............................................X........................................X.X..................................................................X...........................................X .....................................X....................................................................................................................................X.X........X...............X.. ................................X......X...............................X....................................................X..............................X............................................ .............X.......................................................................................................................................................................................... ...........................................................X............X......................................................................................................................X........ ...........................................................................................................................................................X............................................ ......X........................................................................X.................X...................................................................................................X.. .....X..................................................................X............................................................................................................................... .........................................................................................................................................................X.............................................. .............................X.....................................................X.........................................................X.......................................................... ...........................X....................................................X.......X............................................X........X.......................................X................. .........................................X.....................................................................X.......................X..................................................X............. .X................................................................................................................................X..................................................................... ........................................................X...........................X.................X......................X.......................................................................... ......X..........................................................X...............X....................X....................X...........X.X.....................X..X..................................... XX..................................................................XXX................................................................................................................................. ....X.......X..................................X.....................XXX...........................X..............................................X.............................................X....... ...................X........X.................................X......XXXX............................................................................................................................... ....................................................................XXXXXXX....................................X....................................X....X...............X.............................. .....................................X.............................XXX..XXXX....X.........................X............................................................................................. ........X.........................................................XXX.....XXX.............................X.................................................X.....................X..X.............X.... .............X...............................X....................XX.......XX........................................................X.................................................................. .................................................................XXX........XX.........X.........................................................................................................X...... ................X...............................................XXXX........XX..X........X...X................X.................X..............................X........................................ ...............................................XX.............XXXX..........XX.................................................................................................X...........X............ .X..........................................X..................XXXX.........XX...XX..........................................X...................X...................................................... .X..........................X.................................XXXXXXX.......XX...XXXX.......................X............X....X.........................X...............................X........X...... .............................................................XXX..XXXX.....XXX....XXX.......................................................................................................X........... ............................................................XXX.....XXXXXXXXX....XXXX.................................................................X................................................. .X...X...................................................XXXXX.....X.XXXXXXX....XXXXX...................X............................................................................................... ................................X........................XXXX..................XXXXX..........................X.......................X................................................X................ ...........................................................XXX................XXX.XX.............................XX..................................................................................... ............................................................XXX...............XX..XX.....................X........X........X.....................X...........................X.......................X.. ..................................................X..........XXX.............XXX..XX...........................................X..........................................................X..........X.. ......................X.......................................XX............XXX...XX.........XX......................................................................................................... .................................X.......................................X.XXX..XXX........XXXXX.....X...........................................................................X...................... ..........X................................X....X.....X....................XX....XX.....XXXXXXXXX....................................................................................................... .....................................................................X....XXX....XX...XXXXXXXX.XX......X..............X................................................................................. ...............................X.........................................XXX....XXX.XXXXX..XX.....XXX...........................................X....................................................... ....................X.................................................XXXXX......XXXXXX...XXX......XXXX................................................................................................. .................................X..X.................................XXXX......XXXXX....XXX........XXX.............................................................X........................X.......... .............X.....X...........................................X.......XXX.......XX.....XXX..........XXXX..................................................X............................................ .........................XX...X................................X........XXX..X..........XX..........XXXXX..................................................X.........................................X.. ..X..........XX.......................................................................XXXX.........XXX.XX................X.............................................................................. ......................................................................................XXX........XXXX..XX...................................X........................................................... .............................................XX......X.........X....X................XXX.......XXXX....XX............................................................................................... ..............................X.....................................................XXX.......XXXX....

Submit solution!

Added by:	Roman Sol
Date:	2008-02-13
Time limit:	1s
Source limit:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:	ZCon 2008

hide comments



2013-05-02 13:15:22 David Davidoviæ Thanks for the info. My bad. I just assumed you feed tests directly from the generator at zcontest.ru.
2013-05-02 13:13:30 Mitch Schwartz @David: "The datasets used for testing are such that all letters of the word are contained inside the picture."
2013-05-02 13:06:19 David Davidoviæ The generator sometimes spawns images where a part of the text is outside the image bounds (as is the case here: http://i.imgur.com/WlbyYdD.png). How am I supposed to treat this, given that even a human can't tell what the clipped letter is?