장터판 (Small)

지리산을 오르다가 장이 선 장터를 지나게 되었다. 사람이 몰린 한쪽에서 누군가 게임을 열고 있다.

이 게임은 탁자에 놓인 $N$행 $M$열 격자판으로 진행한다. 격자의 칸마다 $K$면체 주사위가 하나씩 놓여 있다.

주최자는 주사위 중 일부를 특정 면이 보이도록 고정하고, 나머지는 자유롭게 구르도록 둔다. 그런 다음 판을 흔들면 고정하지 않은 주사위(자유로운 주사위)가 구르다가 $K$개의 면 중 하나를 보인다. 어느 면이 보일 확률은 $K$개 면이 모두 같고, 주사위마다 독립이다.

판이 멈추면 칸마다 점수를 매긴다. 보는 방향은 가로, 세로, 두 대각선의 네 가지다.

1. 그 칸을 포함해 한 방향으로 연속한 4칸이 모두 같은 면을 보이는 경우가 있으면 $S_4$점이다.
2. 1번에 해당하지 않고, 그 칸을 포함해 한 방향으로 연속한 3칸이 모두 같은 면을 보이는 경우가 있으면 $S_3$점이다.
3. 2번에 해당하지 않고, 그 칸을 포함해 한 방향으로 연속한 2칸이 모두 같은 면을 보이는 경우가 있으면 $S_2$점이다.

어느 항목에도 해당하지 않는 칸은 0점이다. 모든 칸의 점수를 더한 값이 그 게임의 점수다.

주사위를 고정하는 작업은 이미 끝났고 이제 판을 흔들 차례다. 판을 흔들었을 때 나오는 점수의 기댓값을 구하라.

첫 줄에 테스트 케이스의 수 $T$가 주어진다.

각 테스트 케이스의 첫 줄에는 정수 여섯 개 $N$, $M$, $K$, $S_4$, $S_3$, $S_2$가 공백으로 구분되어 주어진다. $N$은 판의 행 수, $M$은 열 수, $K$는 주사위의 면 수이고, $S_4$, $S_3$, $S_2$는 위에서 설명한 점수다.

다음 $N$개의 줄은 판의 맨 위 행부터 차례로 그 행에 놓인 주사위의 상태를 나타낸다. 각 줄은 공백 없이 이어진 문자 $M$개로 이루어진다. 고정된 주사위는 보이는 면의 번호인 1부터 $K$까지의 한 자리 숫자로, 자유로운 주사위는 물음표 ?로 적는다.

제한

• $1 \le T \le 50$
• $2 \le N \le 8$, $2 \le M \le 8$
• $2 \le K \le 9$
• $0 \le S_2 \le S_3 \le S_4 \le 100$
• 한 판에 있는 자유로운 주사위는 0개 이상 4개 이하다.

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 그 케이스의 점수 기댓값이다.

$y$는 소수점 아래 일곱째 자리까지 적는다. 여덟째 자리 아래는 가장 가까운 값으로 반올림하고, 정확히 중간인 값은 0에서 먼 쪽으로 올린다. 예를 들어 기댓값이 정확히 $38.42578125$이면 38.4257813을 출력한다. 기댓값이 정수여도 1600.0000000처럼 소수점 아래 일곱 자리를 모두 적는다.