추리 소설 "초콜릿 괴도 레나"를 감명깊게 읽은 코코는 이 소설의 명장면을 따라해 보기로 했다. 구체적인 방법은 다음과 같다.

• 1단계 : 먼저 $N \times N$ 크기의 사각 격자 형태의 초콜릿을 준비한다. 이 초콜릿은 $1 \times 1$ 단위로 원하는 곳에서 떼어낼 수 있게 되어 있으며, 일부분이 제거된 상태이다. 이때, 남아있는 단위 초콜릿은 $4$개 이상이며, 한 조각을 이루어야 한다. 상하좌우로 이웃한 두 단위 초콜릿은 서로 연결되어 있으며, 서로 연결된 단위 초콜릿들의 집합을 하나의 조각이라고 한다.
• 2단계 : 이 초콜릿에서 다음의 조건을 충족하도록 하나의 단위 초콜릿을 떼어 먹는다.
  • 이 단위 초콜릿을 떼어낸 후에도 남아있는 초콜릿은 하나의 조각을 이루지만, 그 이후에 서로 이웃한 임의의 두 단위 초콜릿 사이를 자르면 $2$개의 조각으로 나누어진다.
• 3단계 : 레나의 명대사를 외친다. "이번엔 봐줬지만, 다음에는 반드시 초콜릿을 조각내 줄 거야."

코코는 1단계의 조건을 충족하는 초콜릿을 준비해 놓았지만, 2단계의 조건을 충족하려면 어느 지점에 있는 단위 초콜릿을 떼어내야 할지 고민에 빠졌다. 코코를 도와주자.

Input

첫 번째 줄에는 초콜릿의 크기 $N$이 주어진다. $(2 \le N \le 1\,000)$

두 번째 줄부터 $N$줄에 걸쳐서 초콜릿의 상태가 주어진다. 각 줄에는 각 칸에 단위 초콜릿이 있는지를 나타내는 문자 $N$개가 공백 없이 주어진다. 각 문자는 모두 # 또는 .이며, 초콜릿의 $r$번째 줄의 $c$번째 글자가 #이면 $r$행 $c$열에 단위 초콜릿이 있음을, .이면 없음을 뜻한다. 초콜릿의 맨 왼쪽 위 칸은 $1$행 $1$열이다.

모든 입력은 1단계의 조건을 충족한다.

Output

첫 번째 줄에는 2단계의 조건을 충족하도록 떼어낼 수 있는 서로 다른 단위 초콜릿의 개수를 출력한다.

다음 줄부터는 그러한 단위 초콜릿의 행 번호와 열 번호를 한 줄에 하나씩 출력한다. 이때, 행 번호가 작은 것부터, 행 번호가 같은 것들 중에서는 열 번호가 작은 것부터 출력한다.

Examples

Input 1

3
###
#.#
###

Output 1

8
1 1
1 2
1 3
2 1
2 3
3 1
3 2
3 3

Input 2

3
##.
###
###

Output 2

1
2 2