Mr. Bean’s uncle gifted him 15 English letter toys from 'a' to 'o'. As Mr. Bean is a joker, no one was willing to play with him. So he sat on the floor and arranged these toys in ascending order i.e. “abcdefghijklmno”. Then he figured out the next greatest string in lexicographic order that can be formed by rearranging the toys is “abcdefghijklmon”. Now he is learning programming and wants to write a program to solve the following problem: Given a string S which can be formed by rearranging the toys, find the N-th greater string in lexicographic order. You can safely assume that such a string always exists.

Input

The first line contains a natural number T denoting the number of test cases. Next T lines contain the description of T test cases, each with string S and value N.

Output

For each test case print the answer in a separate line.

Constraints

1 <= t <= 1000

2 <= S.length() <= 15

'a' <= S[i] <= 'a' + S.length() - 1

All letters in S are unique.

Sample

Input:
3
abdc 2
adcb 3
badc 7

Output:
acdb
bcad
cbad