격납고 화물 운반

비행기 조립 라인이 들어갈 새 격납고의 건설 도면을 검토한다. 격납고 바닥은 $n$개의 행과 $n$개의 열로 이루어진 정사각형 격자이고, 각 칸은 빈 칸이거나 막힌 칸이다. 행은 위에서 아래로 $1$부터 $n$까지, 열은 왼쪽에서 오른쪽으로 $1$부터 $n$까지 번호가 붙어 있다.

비행기 부품이 담긴 큰 화물은 바닥 위의 여러 위치 사이를 자유롭게 옮길 수 있어야 한다. 화물은 격자에 맞춰 놓인 정사각형이고 항상 한 칸을 중심으로 놓인다. 따라서 홀수 $k$에 대해 크기가 $k$인 화물은 연속한 $k$개의 행과 연속한 $k$개의 열이 겹치는 칸을 모두 덮는다. 화물은 한 번에 위, 아래, 왼쪽, 오른쪽 중 한 방향으로 한 칸씩 옮길 수 있고, 옮긴 뒤에도 격자 안에 완전히 들어와 있어야 하며 막힌 칸을 덮어서는 안 된다.

칸의 쌍 $A_k$와 $B_k$가 $q$개 주어진다. 각 쌍마다 $A_k$를 중심으로 놓았다가 바닥 위를 옮겨서 $B_k$를 중심으로 놓을 수 있는 화물의 최대 크기를 구한다.

첫째 줄에 격납고 바닥의 한 변 길이 $n$ ($2 \le n \le 1000$)이 주어진다.

다음 $n$개의 줄에는 바닥의 한 행을 나타내는 길이 $n$의 문자열이 주어진다. 문자 #은 막힌 칸, 문자 .은 빈 칸이다.

다음 줄에 질의의 개수 $q$ ($1 \le q \le 300\,000$)가 주어진다. 이어지는 $q$개의 줄에는 각각 네 정수 $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$번째 줄에는 $A_k$에서 $B_k$까지 옮길 수 있는 화물의 최대 크기 $s_k$를 정수 하나로 출력한다. $A_k$에서 $B_k$까지 옮길 수 있는 화물이 없으면 $s_k$는 $0$이다. 크기가 $1$인 화물은 한 칸만 덮으므로, $s_k$가 $0$인 경우는 크기 $1$인 화물조차 $A_k$에서 $B_k$로 옮길 수 없는 경우뿐이다.