给你一个拥有 $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} = \text{o}$。
• 如果 $i$ 是奇数且 $j$ 是偶数，则 $S_{i,j} = \text{-}$ 或 $\text{.}$。
• 如果 $i$ 是偶数且 $j$ 是奇数，则 $S_{i,j} = \text{|}$ 或 $\text{.}$。
• 如果 $i$ 是偶数且 $j$ 是偶数，则 $S_{i,j} = \text{.}$。

给你 $Q$ 个独立的查询。在第 $i$ 个查询（$1 \le i \le Q$）中，给定奇数 $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]$ 中，将字符 $\text{o}$ 视为顶点，将字符 $\text{-}$ 和 $\text{|}$ 视为边。得到的无向图有多少个连通分量？

更具体地，回答以下问题：

考虑一个拥有 $((D_i - U_i + 2)/2) \times ((R_i - L_i + 2)/2)$ 个顶点的无向图 $G$。每个顶点对应一个二元组 $(x, y)$，其中 $x$ 是满足 $U_i \le x \le D_i$ 的奇数，$y$ 是满足 $L_i \le y \le R_i$ 的奇数。

无向图 $G$ 包含以下边，且不包含其他边：

• 如果奇数 $x, y$ 满足 $U_i \le x \le D_i$，$L_i \le y \le R_i - 2$，且 $S_{x,y+1} = \text{-}$，则在顶点 $(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} = \text{|}$，则在顶点 $(x, y)$ 和 $(x + 2, y)$ 之间存在一条无向边。

求无向图 $G$ 的连通分量个数。

输入格式

输入按以下格式给出：

N
S1,1S1,2 ... S1,2N+1
S2,1S2,2 ... S2,2N+1
:
S2N+1,1S2N+1,2 ... S2N+1,2N+1
Q
U1 D1 L1 R1
U2 D2 L2 R2
:
UQ DQ LQ RQ

输出格式

输出 $Q$ 行。对于 $i = 1, 2, \dots, Q$，在第 $i$ 行输出第 $i$ 个查询的答案。

数据范围

• $N$ 是满足 $1 \le N \le 2000$ 的整数。
• 如果 $i$ 是奇数且 $j$ 是奇数，则 $S_{i,j} = \text{o}$。
• 如果 $i$ 是奇数且 $j$ 是偶数，则 $S_{i,j} = \text{-}$ 或 $\text{.}$。
• 如果 $i$ 是偶数且 $j$ 是奇数，则 $S_{i,j} = \text{|}$ 或 $\text{.}$。
• 如果 $i$ 是偶数且 $j$ 是偶数，则 $S_{i,j} = \text{.}$。
• $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

说明

给定的网格如下所示：

第一组查询的答案是 4，如下图所示。