로고

한 회사의 로고는 단위 정사각형으로 나뉜 직사각형 격자 위에서 일부 칸을 검게 칠해 디자인합니다. 간판은 직사각형 바탕 위에 금박 조각을 붙여서 만드는데, 완성된 금색 도형이 로고 모양(검게 칠한 칸들의 집합)과 정확히 같아야 합니다. 조각은 회전하거나 뒤집어(양면 모두) 붙일 수 있지만, 서로 겹쳐 붙일 수는 없습니다. 디자인의 각 단위 칸은 $1\,\text{m} \times 1\,\text{m}$ 크기의 금색 정사각형 하나에 대응합니다.

제작사는 몇 가지 모양의 조각을 사용합니다. 각 조각은 한 덩어리로 이어진(변을 맞댄 칸들로 서로 오갈 수 있는) 단위 정사각형들의 집합이며, $3 \times 3$ 틀에서 아홉 칸 중 일부를 잘라내어 찍어냅니다.

각 주문(디자인)에 대해, 주어진 조각 모양만으로 그 간판을 만들 수 있는지 판정하고, 만들 수 있다면 필요한 조각의 최소 개수를 구하세요.

다음을 수행하는 프로그램을 작성하세요.

• 제작사가 사용하는 조각 모양들을 읽어 들인다,
• 간판 디자인들을 읽어 들인다,
• 각 디자인에 대해 제작 가능 여부를 판정하고, 가능하면 필요한 조각의 최소 개수를 계산한다,
• 결과를 표준 출력에 출력한다.

첫 줄에는 제작사가 사용하는 조각 모양의 개수 $n$ ($1 \le n \le 5$)이 주어집니다.

이어서 $n$개의 조각 모양 설명이 주어집니다. 각 모양은 3개의 줄로 이루어지며, 각 줄은 3개의 문자로 되어 있습니다. #은 그 칸이 조각에 속함을, .은 그 칸이 틀에서 잘려 나갔음을 뜻합니다.

그다음 줄에는 디자인의 개수 $m$ ($1 \le m \le 3$)이 주어집니다.

이어서 $m$개의 디자인 설명이 주어집니다. 각 디자인은 두 정수 $x$, $y$ ($1 \le x \le 55$, $1 \le y \le 5$)로 시작하며, 각각 간판의 너비와 높이(미터 단위)입니다. 다음 $y$개의 줄에는 각각 $x$개의 문자가 있습니다. #은 그 칸이 금색이어야 함을, .은 그 칸이 비어 있어야 함을 뜻합니다.

입력에서 서로 다른 블록(개수 줄, 각 조각 설명, 각 디자인 설명)은 빈 줄 하나로 구분됩니다.

정확히 $m$개의 줄을 출력합니다. $i$번째 줄에는 $i$번째 디자인을 만드는 데 필요한 조각의 최소 개수를 출력하고, 만들 수 없다면 단어 NIE를 출력합니다.