3741 - 贵州大学第五届程序设计竞赛连通的棋子数

通过次数

提交次数

旧版界面

Time Limit : 1 秒 Memory Limit : 128 MB

给定一个N * N的棋盘，计算棋盘上每一个位置的棋子在水平方向、竖直方向以及对角线方向连通的相同棋子的最大数。例如，下面的棋盘上，第1列的黑子的最大连通数都是4，而第1行的第2、3两个黑子的最大连通数是3。位于棋盘对角线上的每个白子的最大连通数都是3，等等。

<img src="http://tk.hustoj.com:80//../file://C:\Users\xujing\AppData\Roaming\Tencent\Users\57409808\QQ\WinTemp\RichOle\CI0YWHMPL4GG93@3N[@(@[E.png" />

<img src="http://tk.hustoj.com:80//../file://C:\Users\xujing\AppData\Roaming\Tencent\Users\57409808\QQ\WinTemp\RichOle\CI0YWHMPL4GG93@3N[@(@[E.png" />

<br />

Input

输入包括多组测试数据。每组测试数据的第一行包含一个整数N(0<=N<=1000)代表棋盘的大小，接下来是N行，每行包括N个字母，字母为B表示黑子，为W表示白子，为#表示该处没有棋子。N为0表示输入结束。

Output

对每组测试数据，输出N行，每行N个整数分别表示棋盘该处棋子的最大连通数，如果棋盘该处无棋子则应该输出0。

Examples

Input Format

5
B B B # #
B W # W W
B # W # #
B # # W #
# # # # #
0

Output Format