주사위 비밀번호 보안

NCIM 그룹은 국방과 보안 분야의 IT 솔루션과 관련된 일을 많이 한다. 좋은 보안은 대개 강한 비밀번호를 고르는 것에서 시작한다. 비밀번호를 무작위로 생성하는 것은 일반적으로 좋은 방법이다. 예를 들어 “2R4eZ9Rqup” 같은 비밀번호는 “god”, “love”, “sex”, “secret”보다 추측하기 조금 더 어렵다.

무작위 문자와 숫자로 이루어진 비밀번호의 문제는 기억하기 어렵다는 것이다. 문자와 숫자 대신 무작위 단어를 이어 붙여 비밀번호를 생성할 수도 있다. 단어는 문자와 숫자보다 기억하기 쉽다. 7776($6^5$)개의 단어로 이루어진 사전을 사용하면, 무작위 단어 5개로 만든 비밀번호는 무작위 문자 11개로 만든 비밀번호와 비슷한 강도를 가진다.

$7776^5 = 28430288029929701376 \approx 3 \cdot 10^{19}$

$62^{11} = 52036560683837093888 \approx 5 \cdot 10^{19}$

일부 응용 프로그램은 화면에 점이나 별표를 출력해 입력 중인 비밀번호를 가린다. 그러면 화면을 보는 사람이 비밀번호의 문자 개수를 셀 수 있다. NCIM 그룹은 이것이 비밀번호의 강도를 약화시키는지 알아보려 한다.

다음이 주어졌을 때 생성할 수 있는 비밀번호의 개수를 계산하는 프로그램을 작성해야 한다.

• 단어 사전,
• 비밀번호를 생성하는 데 사용하는 단어의 개수,
• 비밀번호의 길이.

첫째 줄에 정수 $t$ ($1 \le t \le 100$)가 주어진다. 이는 테스트 케이스의 수이다. 그다음 각 테스트 케이스마다 다음이 주어진다.

• 양의 정수 $m$ ($1 \le m \le 7776$), $n$ ($1 \le n \le 5$), $q$ ($1 \le q \le 20$)가 있는 한 줄. 각각 사전에 있는 단어의 개수, 비밀번호를 생성하는 데 사용하는 단어의 개수, 질의의 개수이다.
• 사전: 한 줄에 한 단어씩 $m$개의 줄에 $w_i$가 주어진다. 각 단어는 소문자로만 이루어진다. 각 단어의 길이는 3 이상 10 이하이다. 사전의 어떤 단어도 사전의 다른 단어의 부분 문자열이 아니다.
• $q$개의 줄에 양의 정수 $l_j$ ($1 \le l_j \le 50$)가 주어진다. 이는 관측된 길이이다.

각 테스트 케이스마다 다음을 출력한다.

• $q$개의 줄에 길이가 $l_j$인 가능한 비밀번호의 개수를 출력한다. 이 수는 $2^{63}$보다 작다.