神奇的国度

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

小雷有一天又穿越了,他来到了一个神奇的地方。
既然穿越了,那么要解决的第一件事情就是语言问题,不过解决语言问题之前,小雷发现这个地方的数字表示和我们的不太一样,在潜心研究五年之后发现。这个世界和我们的世界和我们的世界不同的是他们有一个叫做进制模式的东西,每一个进制模式都包括一个整数,和一些字符,整数代表该模式的进制,字符代表从0n-1的每一个数,值得注意的是一个模式中的字符可能重复,这个时候他们会使用其他的方法来表示这个数,不过为了简化问题,其他方法我们不予考虑。
小雷现在需要
需要解决的问题是,知道一个该世界的数字和该数字对应的模式,你能算出这个数字十进制下最小是多少吗?
(字符仅包括 0 ~ 9 , a ~ z , A ~ Z , [ ] , { } , ( ) , < > 

Input

多组输入,第一行一个整数T代表组数
每一组输入第一行为一个整数n2 < = n < = 100,代表该模式的进制
随后一行有n个字符,以空格分开,表示从0n-1n个数
然后有一个整数m,代表要求的数字的位数
再然后有m个字符(保证在之前给出的n个字符中出现),表示要求的数字,从高位到低位,以空格隔开 

Output

每组数据输出一行代表这个数在十进制表示下的最小数
(保证最后的结果小于2^63

Sample Input

2
2 
0 1
3
1 0 0
3
a a c
2
c a

Sample Output

4
6

Hint

 

Source

QAsQ 2015级ACM集训队第二次选拔赛