Petoris

당신은 petoris라는 퍼즐 게임을 하고 있다. 이 게임은 정사각형 격자로 나뉜 보드와, 각각 하나의 격자에 맞는 정사각형 타일로 진행된다.

게임의 각 단계에서 타일이 일부 채워진 보드가 주어진다. 또한 여러 타일로 이루어진 블록도 하나 주어진다. 다음 배치 제약에 따라 이 블록을 보드 어딘가에 놓거나 버려야 한다.

• 블록은 회전할 수 있지만, 나눌 수 없고 뒤집을 수도 없다.
• 블록의 어떤 타일도 보드에 이미 있는 타일과 충돌해서는 안 된다.
• 블록의 모든 타일은 보드 안에 놓여야 한다.

이번 단계에서 얻을 수 있는 최대 점수를 구하는 프로그램을 작성하시오. 점수는 블록을 놓은 뒤 타일로 완전히 채워진 가로줄의 개수이며, 블록을 버리는 경우에는 -1이다.

입력의 첫 줄은 데이터 세트의 수 N이다. 그다음 N개의 데이터 세트가 이어진다.

각 데이터 세트는 블록과 보드를 설명하는 줄로 이루어진다. 블록과 보드의 설명은 모두 세로와 가로 크기를 나타내는 두 정수 H와 W가 있는 줄로 시작한다. 그다음 H개의 줄이 이어지며, 각 줄에는 W개의 문자가 있다. '#'은 타일, '.'은 빈칸을 나타낸다. 0 < H ≤ 64, 0 < W ≤ 64라고 가정할 수 있다. 각 블록은 하나 이상의 타일로 이루어지며 모든 타일은 서로 연결되어 있다. 각 보드는 0개 이상의 타일을 포함하며, 처음 상태에서 타일로 완전히 채워진 가로줄은 없다.

각 데이터 세트마다 얻을 수 있는 최대 점수를 한 줄에 출력한다.