statement.md

Description

西早稲田のとある町の工場が何者かの手によって突然爆発しました！

あなたは町の地図をもとにその原因を突き止めることを依頼されました。

町にはただ１つの工場があり、また、いたるところにビルと爆弾が設置されています。 この町は高さ $M$ 、幅 $N$ のマス目状の形で表すことができます。 町の地図は $M$ 個の長さ $N$ の文字列で表されます。 $i$ $(1 \leq i \leq M)$ 番目の文字列の $j$ $(1 \leq j \leq N)$ 番目の文字は上から $i$ 番目、左から $j$ 番目のマスに設置されているものを表しています。地図上では、工場は'W'、ビルは'#'、爆弾は'1'-'9'の数字（数は大きさを表す）、何もないところは'.'で表されています。

町に置いてある爆弾は大きさが決まっており、大きさ $X$ の爆弾が「爆発」すると、爆弾を中心として $X$ 個離れたマスまで上下左右4方向に直線状の爆炎が向かっていきます。ただし、途中にビルがある場合爆炎は遮られます。ビル以外のものによって爆炎が遮られることはありません。また、爆炎が町の外まで広がることもありません。

爆炎が別の爆弾に達した場合、その爆弾も「爆発」します。これは連鎖的に起こる場合があります。また、爆炎が工場に達した場合工場も爆発します。

あなたの仕事はこの町の地図が与えられた時に、以下の条件を満たす爆弾の個数を調べることです。

• 条件「最初にその爆弾のみを「爆発」させた時、最終的に工場が爆発する」

この条件を満たす爆弾の個数を調べるプログラムを書いてください！

Constraints

• $1 \leq M, N \leq 100$
• 与えられる地図に含まれる文字は、'W'、'#'、'1'-'9'の数字、'.'のみである。
• 与えられる地図に'W'はちょうど１つだけ含まれる。
• 与えられる地図に爆弾が１つも含まれないこと、地図上の全ての爆弾が上の条件をみたさないことがある。

Small

• $1 \leq M, N \leq 10$

Large

• $95 \leq M, N \leq 100$

Input

1 つの入力ファイルは複数のテストケースからなる。 入力ファイルの最初の一行目にはテストケースの個数 $T$ が記される $(1 \leq T \leq 100)$。 2 行目以降には、$T$ 個のテストケースが記述されており、各テストケースは以下の $M+1$ 行で表される。

$M$ $N$
$S_1$
$S_2$
$\vdots$
$S_M$

1 行目には町の高さ $M$ と幅 $N$ が与えられる。

2 行目からの $M$ 行にはそれぞれ町の地図の $i\ (1 \leq i \leq M)$ 行目を表す長さ $N$ の文字列　$S_i$ が与えられる。

Output

各テストケースに対して、条件を満たす爆弾の個数を出力せよ。

Sample Input

6
3 3
.1.
1W.
..1
1 5
2.W.1
3 5
2.2.2
.#.#.
2.2.W
3 5
2.2.2
#####
2.2.W
10 10
####......
........1.
.8..6..#..
.......#..
..#.......
....4.2...
.5......7.
......W...
.9#.3.....
......####
3 3
...
.W.
...

Sample Output

2
1
5
2
8
0

例えば1つ目のテストケースでは、右下の爆弾が「爆発」した場合、爆炎は工場に届きませんが、それ以外の爆弾が「爆発」した場合、爆炎が工場に届き工場が爆発します。よって条件を満たす爆弾の個数は2です。

例えば2つ目のテストケースでは、右の爆弾が「爆発」した場合、爆炎は工場に届きませんが、左の爆弾が「爆発」した場合、爆炎が工場に届き工場が爆発します。よって条件を満たす爆弾の個数は1です。

また、3つ目や4つ目、5つ目のテストケースのように連鎖的に爆弾が「爆発」し、それによって工場が爆発してしまうことがあります。

最後のテストケースのように与えられる地図に爆弾が１つも含まれないことがあることに注意してください。 （工場の爆発は爆弾が原因ではなかったようです。）