Description
Gamebox is developing a new augmented reality game for young kids. Players interact with the virtual object on screen through movements of markers. A marker is a square playing card with special marking. Markers all have different markings. The game is played by showing a marker to the game console. The game console has a hidden video camera that can automatically locate and take a snapshot of the marker being played. Depending on how the card is being held and the distance from the game console, the captured image of the marker maybe displaced from the upright position. Furthermore, noise may be introduced during the imaging process. The marker is then recognized and the game is played accordingly. Obviously, if the marker were incorrectly recognized, then the game would not be played correctly. You are hired as a game programmer to make sure that the markers are recognized correctly.
Constraints:
- All the images are binary images (containing only two colors: black and white). 0 denotes black pixel and 1 denotes white pixel.
- There are 5 markers. Each has been digitized into a 100 x 100 image. The images are shown and described below in graphical form.
- The captured image (test images) can be
- Rotated: in 0, 90, 180, or 270 degree angle.
- Enlarged/shrunk: image size can be of size 50 x 50, 100 x 100, 150 x 150, or 200 x 200.
- Contains random noise: at most 3% of the pixels in the input image are reverted. Black becomes white or vise versa.
- Any combination of the above conditions.
Input
The input file contains a set of test images. Each test image is defined by a single integer n on one line to indicate the image size ( n x n). This number is either 0, 50, 100, 150, or 200. 0 indicates the end of the test data. This is followed by n rows of n consecutive 0s and 1s, which defines the captured image to be processed.
Output
For each input case, output a single integer on one line indicating the marker that matches with the given input image.
Figure 3: Markers 1, 2, 3, 4, and 5 from left to right.