Hey, hello! Yes, I am talking to you, whoever is reading this problem statement. I know you are Robin, the sidekick to the Batman. As you know Batman is too busy forming the Justice League, he wants you to solve a problem for him.
Flash found that Darkseid is preparing his army to attack the Earth. With the help of Green Lantern he collected a picture of Darkseid’s army training ground where a group of troopers were moving in a line. They think the actual number of troopers in the army is "Square of the number of troopers in the captured image".
Now they need your help to determine the actual size of the army.
They won't provide you the original image instead they will provide you a N*N grid. Each cell of the grid either contains '.' or '*'. A cell that contains '*' represents a trooper.
Flash and Green Lantern are also aware of the fact that their image might be corrupted so they also want you to inform them if the image is corrupted.
Troopers only move in one single straight line so the image is corrupted if all the troopers are not in a single line or if there are no troopers at all.
In summary, you need to do the following task:
1. If troopers are in a straight line then calculate the actual number of troopers in the army.
2. If troopers are not in a straight line or there are multiple straight lines of troopers or no troopers at all then the image must be corrupted so inform accordingly.
Input
The first line of input will contain an integer that represents the value of N<=250.
Next N lines will contain N characters, and each of the characters will be either '.' or '*'.
Output
If the image is valid print the actual number of troopers in the army otherwise print "Corrupted Image".
Samples
| Input | Output |
|---|---|
3 ... *** ... | 9 |
Here all the cells of the second row contain ‘*‘ representing 3 troopers standing in a single line, so the image is not corrupted. Actual number of troopers is 3*3 = 9. | |
| Input | Output |
|---|---|
5 ....* ...*. ..... .*... *.... | Corrupted Image |
Here total 4 troopers can be seen but they are in two different lines, so image is corrupted. | |
