Big MOD is a very intelligent boy. He likes mathematics and mathematical games. He often challenge his friends in various mathematical games. But all his friends are not god at mathematics and when Big MOD challenges his friends and they can’t answer the problem properly he feel very proud.  But today his friend Little MOD who is a great programmer challenge him and give him a problem like this-

Little MOD give him two integer number N and K and ask him what is the maximum and minimum number can be get from N after deleting exactly K digits from N without changing the order of the digits.

Though Big MOD is good at mathematics but he is not good in programming and he wants to win this challenge so he wants your help to solve this problem. Can you help Big MOD to defeat Little MOD in this game ?

Input

Input starts with an integer (T≤200) which denotes the number of test case. Each test case consists of two integers N and Q (0<=N<=10^18 and 1<=Q<=100) Where N is the given Number by Little MOD and Q is the number of query. The next line contains Q space separated integers which denotes the value of K ( 0<=K<=|N|) Here |N| denotes the number of digits in N.

Output

For each test case, print the case number at first then for each K given in query print the maximum and the minimum integer number which are the answer for Big MOD in the above game. Keep in mind that for an empty number Big MOD need to say 0.

See the sample input and output for better understanding.

Example

Input:
2
1234 2
1 2
1578 1
3
Output:
Case 1:
234 123
34 12
Case 2:
8 1