한글 결여 수

세종대왕이 펴낸 훈민정음해례본은 1962년에 국보 70호로 지정되었다. 한글의 우수성을 알리고 훈민정음 창제와 반포를 기념하기 위해, 한글이 반포된 날인 매년 10월 9일은 국경일인 한글날로 지정되어 있다.

한글날을 기념하여 수를 한글로 적어 보자. $1$부터 $10^{52} - 1$까지의 수는 일반적인 한글 수 표기를 따르되, 표기가 여러 방식으로 달라질 수 있으므로 이 문제에서는 아래 문법으로 통일한다.

<기수 1> = '일' | '이' | '삼' | '사' | '오' | '육' | '칠' | '팔' | '구'
<기수 2> = '십' | '백' | '천'
<기수 3> = '만' | '억' | '조' | '경' | '해' | '자' | '양' | '구' | '간' | '정' | '재' | '극'
<기수 4> = <기수 1> | <기수 1> <기수 2> | <기수 1> <기수 2> <기수 4>
<수의 한글 표기> = <기수 4> | <기수 4> <기수 3> | <기수 4> <기수 3> <수의 한글 표기>

예를 들어 $1234,5678,9099,8808,7770,0666,0055,4004,3300,0002,1000,0000,1962$는 "일천이백삼십사극오천육백칠십팔재구천구십구정팔천팔백팔간칠천칠백칠십구육백육십육양오십오자사천사해삼천삼백경이조일천억일천구백육십이"라고 쓰고, $21,4748,3647$는 "이십일억사천칠백사십팔만삼천육백사십칠"이라고 쓴다.

우리 세계에는 한글의 자음과 모음이 모두 있으므로 위 규칙을 그대로 사용할 수 있다. 이제 일부 자음과 모음이 없는 평행 세계를 생각해 보자. 예를 들어 ㅇ이 없는 세계에서는 우리 세계의 수 표기에 ㅇ이 들어가는 수는 존재하지 않는 수로 본다. 따라서 $1$(일)과 $2$(이)는 존재하지 않고, $3$(삼)이 첫 번째 양의 정수가 된다.

우리 세계에는 항하사, 아승기, 나유타, 불가사의, 무량대수처럼 더 큰 수를 나타내는 단위도 있지만, 이 문제에서는 사용하지 않는다. 어떤 수가 너무 커서 위 문법으로 적을 수 없다면 그 수 역시 존재하지 않는 수로 본다.

일부 자음과 모음이 없는 평행 세계에서의 $N$번째 양의 정수를 우리 세계의 아라비아 숫자로 출력하라.

첫 번째 줄에 테스트 케이스의 개수 $T$가 주어진다. $(1 le T le 1,000)$

각 테스트 케이스의 첫 번째 줄에는 양의 정수 $N$과, 평행 세계에 없는 자음과 모음의 개수 $M$이 공백으로 구분되어 주어진다. $(1 le N le 10^{52} - 1$; $1 le M le 21)$

각 테스트 케이스의 두 번째 줄에는 평행 세계에 없는 자음과 모음이 중복 없이 공백으로 구분되어 주어진다. 자음은 ㄱ, ㄴ, ㄹ, ㅁ, ㅂ, ㅅ, ㅇ, ㅈ, ㅊ, ㅍ, ㅎ 중에서만 주어진다. 모음은 ㅏ, ㅐ, ㅑ, ㅓ, ㅕ, ㅗ, ㅜ, ㅠ, ㅡ, ㅣ 중에서만 주어진다.

모든 입력은 UTF-8로 인코딩되어 주어진다.