您正在评估一个巨型新机库的施工计划，该机库将容纳一条飞机装配线。机库地面可以用一个由 $n$ 行 $n$ 列组成的矩形网格来表示，其中每个单元格要么是空的，要么是阻塞的。行号从上到下依次为 $1$ 到 $n$，列号从左到右依次为 $1$ 到 $n$。

重要的是，装有飞机零件的大型板条箱可以在机库内的不同位置之间自由移动。我们可以将板条箱建模为一个与网格单元对齐并以其中一个单元格为中心的正方形。因此，对于奇数 $k$，大小为 $k$ 的板条箱由 $k$ 个连续行和 $k$ 个连续列中的单元格组成。只要板条箱完全位于网格内且不包含任何阻塞单元格，它就可以向上、向下、向左或向右移动。

给定 $q$ 对单元格 $A_k$ 和 $B_k$。对于每一对，求出可以以 $A_k$ 为中心，并移动到以 $B_k$ 为中心的最大的板条箱尺寸。

输入格式

第一行包含一个整数 $n$ ($2 \le n \le 1000$)，表示机库地面的大小。接下来的 $n$ 行，每行包含一个长度为 $n$ 的字符串，描述地面的一行。字符 “#” 表示阻塞单元格，字符 “.” 表示空单元格。

下一行包含一个整数 $q$ ($1 \le q \le 300\,000$)，表示查询次数。接下来的 $q$ 行中，第 $k$ 行包含四个整数 $r_{A_k}, c_{A_k}, r_{B_k}, c_{B_k}$ ($1 \le r_{A_k}, c_{A_k}, r_{B_k}, c_{B_k} \le n$)，分别表示单元格 $A_k$ 和 $B_k$ 的行号和列号。单元格 $A_k$ 与单元格 $B_k$ 不同。此外，这两个单元格始终为空。

输出格式

输出 $q$ 行。第 $k$ 行应包含一个整数 $s_k$，表示可以从 $A_k$ 移动到 $B_k$ 的最大板条箱尺寸。如果没有任何板条箱可以从 $A_k$ 移动到 $B_k$，则 $s_k$ 应为 $0$。

样例

输入格式 1

7
....#.
..#.#.
....#.
...###
....#.
#.....
......
5
2 5 5 2
2 5 3 6
2 2 6 3
2 2 6 6
1 1 7 7

输出格式 1

1
0
3
1
1