1962번 - 한글 ㄴㄴ 수

세종대왕이 펴낸 훈민정음해례본은 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$개의 테스트 케이스가 입력으로 주어지며, 첫 번째 줄에 $T$가 주어진다. $(1 \le T \le 1\,000)$

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

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

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

각 줄에 각 테스트 케이스마다 평행 세계에서의 $N$번째 양의 정수가

• 존재한다면 우리 세계의 아라비아 숫자로 출력한다.
• 존재하지 않는다면 -1을 출력한다.