큰 버튼

당신은 인기 있는 새 게임 쇼의 참가자이며, 큰 상금을 놓고 게임을 하고 있다.

빨간 버튼과 검은 버튼, 두 개의 큰 버튼이 있다. 당신은 정확히 N번의 버튼 누르기 순서를 만든다.

만들 수 있는 순서는 많지만, 길이가 N 이하인 P개의 금지된 접두사가 있다. 만든 순서가 금지된 순서 중 어느 하나로 시작하면 큰 상금을 받지 못한다. 순서 중간에 금지된 접두사가 하나 이상 나타나는 것은 괜찮다. 단, 순서의 맨 앞에 나타나면 안 된다.

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

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

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

• 1 ≤ T ≤ 100.
• 1 ≤ P ≤ min(2N, 100).
• 각 금지된 접두사의 길이는 1자 이상 N자 이하이다.
• 두 금지된 접두사가 같지 않다.