큰 버튼

당신은 인기 있는 새로운 게임 쇼의 참가자이며, 대상에 도전하고 있다!

큰 버튼이 두 개 있으며, 하나는 빨간색이고 하나는 검은색이다. 정확히 N번 버튼을 누르는 수열을 만들 것이다.

만들 수 있는 서로 다른 버튼 누르기 수열은 많지만, 길이가 N 이하인 금지 접두사가 P개 있다. 금지된 수열 중 어느 하나로 시작하는 버튼 누르기 수열을 만들면 대상을 받을 수 없다. 하나 이상의 금지 접두사가 수열의 시작 부분에 나타나지 않는 한, 수열에 포함되어도 괜찮다.

우승 수열은 정확히 N번의 버튼 누르기로 이루어져야 하며 금지 접두사 중 하나로 시작해서는 안 된다. 서로 다른 우승 수열은 몇 개인가?

제한

1 ≤ T ≤ 100. 시간 제한: 테스트 세트당 20초. 메모리 제한: 1 GB. 1 ≤ P ≤ min($2^{N}$, 100). 각 금지 접두사의 길이는 1자 이상 N자 이하이다. 두 금지 접두사가 같은 경우는 없다.

테스트 세트 1

1 ≤ N ≤ 10.

테스트 세트 2

1 ≤ N ≤ 50.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 위에서 설명한 두 정수 N과 P가 포함된 한 줄로 시작한다. 그다음 P개의 줄이 더 주어지며, 각 줄에는 길이가 1자 이상 N자 이하인 문자열이 주어지고, 이 문자열은 금지된 버튼 누르기 수열 중 하나를 나타낸다. R는 빨간색 버튼을 누르는 것을 나타내고, B는 검은색 버튼을 누르는 것을 나타낸다.

각 테스트 케이스마다 Case #x: y를 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호이며(1부터 시작), y는 위에서 설명한 우승 수열의 개수이다.

마지막 예제 케이스는 소규모 데이터 세트에는 등장하지 않는다는 점에 유의한다.

첫 번째 케이스에서는 3번 누르는 수열을 만들어야 한다. 세 번 누르는 가능한 수열은 8개이지만, 그중 일부는 게임에서 패배하게 만든다. 그 수열들은 아래와 같다.

• RBB. 첫 번째 금지 수열(RB)로 시작하므로 금지된다.

• RBR. 첫 번째 금지 수열(RB)로 시작하므로 금지된다.

• BBB. 두 번째 금지 수열(BBB)로 시작하므로 금지된다.

따라서 우승 수열은 5개뿐이다.

두 번째 케이스에서는 5번 누르는 수열을 만들어야 한다. 금지 수열은 R 하나뿐이다. 이는 첫 번째로 B 버튼을 눌러야 하고, 그다음 4번은 두 버튼 중 어느 것을 눌러도 된다는 뜻이다. 따라서 서로 다른 버튼 누르기는 총 16개가 된다.

세 번째 케이스에서는 4번 누르는 수열을 만들어야 한다. 금지 수열이 세 개 있지만, 가능한 모든 수열이 R(첫 번째 금지 수열) 또는 B(두 번째 금지 수열)로 시작하므로 우승 수열은 없다. 따라서 정답은 0이다.