Hangul-Missing Numbers

The Hunminjeongeum Haerye manuscript published by King Sejong was designated National Treasure No. 70 in 1962. To celebrate the excellence of Hangul and commemorate the creation and proclamation of Hunminjeongeum, October 9 of every year is designated as the national holiday Hangul Day.

To celebrate Hangul Day, write numbers in Hangul. Numbers from $1$ through $10^{52} - 1$ are written using the usual Korean notation for numbers. Since that notation can vary by context, this problem uses the following grammar as the unified notation.

<cardinal 1> = '일' | '이' | '삼' | '사' | '오' | '육' | '칠' | '팔' | '구'
<cardinal 2> = '십' | '백' | '천'
<cardinal 3> = '만' | '억' | '조' | '경' | '해' | '자' | '양' | '구' | '간' | '정' | '재' | '극'
<cardinal 4> = <cardinal 1> | <cardinal 1> <cardinal 2> | <cardinal 1> <cardinal 2> <cardinal 4>
<Hangul notation of a number> = <cardinal 4> | <cardinal 4> <cardinal 3> | <cardinal 4> <cardinal 3> <Hangul notation of a number>

For instance, $1234\,5678\,9099\,8808\,7770\,0666\,0055\,4004\,3300\,0002\,1000\,0000\,1962$ is written as "일천이백삼십사극오천육백칠십팔재구천구십구정팔천팔백팔간칠천칠백칠십구육백육십육양오십오자사천사해삼천삼백경이조일천억일천구백육십이", and $21\,4748\,3647$ is written as "이십일억사천칠백사십팔만삼천육백사십칠".

In our world, every Hangul consonant and vowel exists, so the rules above can be used as written. Now imagine a parallel world where some consonants and vowels do not exist. In a world without ㅇ, if the Hangul notation of a number in our world contains ㅇ, that number is treated as nonexistent. Therefore $1$(일) and $2$(이) do not exist, and $3$(삼) is the first positive integer.

Our world also has larger-number units such as 항하사, 아승기, 나유타, 불가사의, and 무량대수, but they are not used in this problem. If a number is too large to be written by the grammar above, that number is also treated as nonexistent.

Output the $N$-th positive integer of the parallel world, written as an Arabic numeral in our world.

The first line contains the number of test cases $T$. $(1 le T le 1\,000)$

For each test case, the first line contains a positive integer $N$ and the number $M$ of consonants and vowels that do not exist in the parallel world, separated by a space. $(1 le N le 10^{52} - 1$; $1 le M le 21)$

The second line of each test case contains the missing consonants and vowels, separated by spaces, with no duplicates. Consonants are chosen only from ㄱ, ㄴ, ㄹ, ㅁ, ㅂ, ㅅ, ㅇ, ㅈ, ㅊ, ㅍ, ㅎ. Vowels are chosen only from ㅏ, ㅐ, ㅑ, ㅓ, ㅕ, ㅗ, ㅜ, ㅠ, ㅡ, ㅣ.

All input is encoded in UTF-8.

For each test case, print one line.

• If the $N$-th positive integer exists in the parallel world, print it as an Arabic numeral in our world.
• If it does not exist, print -1.