색깔 구슬 접시

4x4 격자로 구슬 자리 16개가 놓인 정사각형 접시가 있다. 구슬은 하얀 구슬과 초록 구슬 두 종류다. 이 접시로 할 수 있는 action은 여섯 가지다.

• (W) 하얀 구슬을 접시 가운데에 떨어뜨린다.
• (G) 초록 구슬을 접시 가운데에 떨어뜨린다.
• (L) 접시를 왼쪽으로 기울인다.
• (R) 접시를 오른쪽으로 기울인다.
• (T) 접시를 위쪽으로 기울인다.
• (B) 접시를 아래쪽으로 기울인다.

가운데에 떨어뜨린 구슬은 가운데 2x2 자리 네 곳의 상태에 따라 들어갈 곳이 정해진다.

• 네 자리가 모두 비어 있으면 네 곳 중 한 곳에 각각 확률 $1/4$로 들어간다.
• 세 자리가 비어 있으면 이미 채워진 자리의 대각선 맞은편에 확률 $1$로 들어간다.
• 두 자리가 비어 있으면 남은 두 곳 중 한 곳에 각각 확률 $1/2$로 들어간다.
• 한 자리가 비어 있으면 그 자리에 확률 $1$로 들어간다.
• 네 자리가 모두 차 있으면 접시에 남은 빈자리 중 한 곳에 모두 같은 확률로 들어간다.

접시를 기울이면 중력 때문에 구슬이 움직인다. 왼쪽으로 기울이면 각 구슬은 왼쪽에 빈자리가 없을 때까지 왼쪽으로 붙는다. 나머지 세 방향도 마찬가지다.

E는 빈자리, W는 하얀 구슬, G는 초록 구슬을 뜻한다. 접시가 다음 상태라고 하자.

EWEE
WEGW
GWGE
EEEE

왼쪽으로 기울이면 이렇게 된다.

WEEE
WGWE
GWGE
EEEE

오른쪽으로 기울이면 이렇게 된다.

EEEW
EWGW
EGWG
EEEE

위쪽으로 기울이면 이렇게 된다.

WWGW
GWGE
EEEE
EEEE

아래쪽으로 기울이면 이렇게 된다.

EEEE
EEEE
WWGE
GWGW

action $N$개와 접시 상태 하나가 주어진다. 빈 접시에서 시작해 action을 주어진 순서대로 모두 수행했을 때, 접시가 주어진 상태와 같아질 확률을 구하라.

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

각 테스트 케이스의 첫 줄에는 action의 개수 $N$ ($0 \le N \le 16$)과 action $N$개가 공백으로 구분되어 주어진다. 각 action은 W, G, L, R, T, B 중 하나다.

이어지는 네 줄에는 목표로 하는 접시 상태가 한 줄에 문자 네 개씩 주어진다. 각 문자는 E, W, G 중 하나다.

각 테스트 케이스마다 한 줄에 확률을 출력한다. 소수점 아래 여섯째 자리까지 반올림하고, 여섯 자리를 모두 채워서 출력한다. 확률이 $1$이면 1.000000, $0$이면 0.000000을 출력한다.