Problem - 3036

R's girl friend D is on military training somewhere near Harbin. She feels bad every day and night. She complains about every terrible thing to R. And sometimes she would wail loudly that she had hurt her foot.

R has a motto, which is "Finding her is my lifetime fate, yet cherishing her is my daily job." So he made a plan, which called "Prison Break", as you know, the same with the famouse American play.

R found out that there were several holes on the wire netting which surrounds the military camp. Or maybe, just R did that. Whatever, R told this to his girl friend D. D gathered the girl comrades, and they decided to escape this night. To help to make the escape safe, R investigated the camp again. And something worse found was soldiers walked guard even in the night. But the good news was they drunk much every night and they were dozing off every night.

The girls' escape, will not make no sound. Once they take action, the evil commander will send his soldiers(not the drunk ones of course) to stop them. You can assume that the soldiers will get there after T seconds. So if they take more time than T, they will get caught.

Initially, there is one person on every empty square in the camp and these persons should move to a hole on the wire netting to exit. They can move one square per second to the North, South, East or West. While escaping, multiple persons can be on a single square. The holes are narrow, however, and only one person can leave through a hole per second.

Now, R and D wants to know whether this action will be successful.If successful, then how much time it will take to get out from the camp.

Multiple cases.
Each test case has the following format:

One line with three integers r, c and T , separated by a single space, satisfying 3 <= r, c <= 12: the size of the camp

Then r lines with c characters descripes the camp.

Girls represented by a '.' . Drunk soldiers and the wire netting represented by an 'X', you can assume that the drunk ones will not move even one square. And the hole is 'E', meaning an exit to the girls.

Input file ends with EOF.

Escape