注意

この問題のメモリ制限は 384 MiB です。

問題文

2N+1 行 2N+1 列のグリッドが与えられます。ここで、 N は正整数です。グリッドの上から i 行目、左から j 列目のマス (1 \le i, j \le 2N + 1) をマス (i, j) と表記します。マス (i, j) には文字 S_{i,j} が書かれており、次の性質を満たします。

• i が奇数、 j が奇数であるとき、 S_{i, j} = o
• i が奇数、 j が偶数であるとき、 S_{i, j} = - または .
• i が偶数、 j が奇数であるとき、 S_{i, j} = | または .
• i が偶数、 j が偶数であるとき、 S_{i, j} = .

独立したクエリが Q 個与えられます。 i 個目 (1 \le i \le N) のクエリでは、奇数 U_i, D_i, L_i, R_i (1 \le U_i \le D_i \le 2N+1,\ 1 \le L_i \le R_i \le 2N+1) が与えられるので、次の問いに答えてください。

部分グリッド [U_i, D_i] \times [L_i, R_i] において、文字 o を頂点、文字 - と | を辺としたときにできる無向グラフの連結成分の個数を求めてください。

厳密には、次に問いに答えてください。

((D_i - U_i + 2) / 2) \times ((R_i - L_i + 2) / 2) 頂点の無向グラフ G があり、頂点は U_i 以上 D_i 以下の奇数 x と L_i 以上 R_i 以下の奇数 y のペア (x, y) で表されるとします。また、無向グラフ G には次の無向辺があるとし、これら以外の無向辺はないとします。

• 奇数 x, y が U_i \le x \le D_i,\ L_i \le y \le R_i - 2 かつ S_{x,y+1} = - を満たすならば、頂点 (x, y) と頂点 (x, y+2) との間に無向辺がある。
• 奇数 x, y が U_i \le x \le D_i - 2,\ L_i \le y \le R_i かつ S_{x+1,y} = | を満たすならば、頂点 (x, y) と頂点 (x+2, y) との間に無向辺がある。

無向グラフ G の連結成分の個数を求めてください。

制約

• N は整数
• 1 \le N \le 2000
• i が奇数、j が奇数であるとき、 S_{i, j} = o
• i が奇数、j が偶数であるとき、 S_{i, j} = - または .
• i が偶数、j が奇数であるとき、 S_{i, j} = | または .
• i が偶数、j が偶数であるとき、 S_{i, j} = .
• Q は整数
• 1 \le Q \le 7000
• 1 \le U_i \le D_i \le 2N+1
• 1 \le L_i \le R_i \le 2N+1
• U_i, D_i, L_i, R_i は奇数

入力例 1

3
o-o-o-o
|.....|
o-o.o.o
|.|....
o-o.o-o
....|.|
o.o-o-o
12
3 5 1 7
1 1 1 1
1 3 1 3
1 3 1 7
1 1 1 1
1 1 1 7
1 7 1 1
1 7 1 7
3 5 3 5
3 5 3 7
3 7 3 7
5 7 3 5

出力例 1

4
1
1
2
1
1
2
4
3
4
4
2

与えられるグリッドは次のようになっています。

1 番目のクエリにおける答えは、次の図のように 4 となります。