Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 2058
The Archaeologist's Trouble II

Time Limit: 2 Seconds      Memory Limit: 65536 KB

Lazy Genius, a Archaelogist, recently found a lot of ancient steles, on which there are only two kinds of characters, '*'and '@'. The characters formed a equilateral triangle on each steles. The triangle has N lines.The ith line contain i characters.

e.g. a triangle with 4 lines:

                     *
                    * @
                   * @ * 
                  @ * @ *

Through hard researchs, he found some rules of arrange of characters. There are only 4 styles of arranges of any three adjacent characters:

       *    @    @    *
      * @, @ *, * @, @ *

Through hundreds of thousands of years, most of steles have become hard to identify. With the rules above, Mr.Genius recovered many steles. However, there are too many steles to be recovered by hand. Now Mr.Genius turns to you, a gifted programming student. He believes that you could help him.

Your task is to find out the maximum number and the minimum number of '@' of a given stele.


Input

The input contains several test cases.

The first line of each test block is a positive integer, N (1 < N <= 100), which represents the size of the triangle.

After that follows N lines. the ith lines contains i characters. The charatcter could only be '@', '*' or '?', where '?' represents the unclear characters.

The input is terminated by a negative integer.


Output

output a line contain two integers for each test block, the maximum and the minimum.


Sample Input

2
*
??
3
?
??
???
5
?
*@
?*?
????
?????
-1


Sample Output

1 1
4 2
9 7



Author: LIN, Zi
Source: ZOJ Monthly, December 2003
Submit    Status