FUNNUMS - FUN WITH LETTERS

no tags 

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

hide comments
nadstratosfer: 2018-01-30 23:28:09

Bugged me for a few days and took quite a while to figure out when I finally sat down to it. Ended up with a strong solution that I'm pretty sure will pay off in the future also. Great problem, the "fun" in the title is no clickbait.

be1035016: 2018-01-17 19:24:52

1 go ac:credit goes to CnC:)

Akshat Mathur: 2015-08-05 16:56:41

Finally AC :-)

Saurabh_P: 2013-12-25 23:53:02

getting tle.... dont get it

Abhinav: 2013-12-17 12:57:29

use long long int ...I got 4 WAs bcoz of that

Kartik Khare: 2013-12-17 12:57:29

just can't figure out why am i getting wrong answer.

BLANKRK: 2013-12-17 12:57:29

m gettin tle again n again.... whts the problm

Aradhya: 2013-12-17 12:57:29

50th user \m/

Aradhya: 2013-12-17 12:57:29

ohh my god.... got loads of wrong answers just because of a silly mistake :P :P.. btw awesome problem ;)

Federico Lebrón: 2013-12-17 12:57:29

I'm not sure I follow. If I have the letters abdc, of all the possible permutations of those letters, the 2nd greatest one lexicographically is dcab (the largest is dcba). Why is the correct answer acdb? And why does it matter that the input is permuted? The lexicographical permutations will be the same (as will their order), regardless of the initial permutation of S.
--ans(francky)--> It's "largest" compared to the given one in input.
Ah, alright, I understand (and AC, after a dumb mistake) then :). I would word it as "the Nth larger word", not largest, but I guess with this comment it's enough to clarify :) Thanks!

Last edit: 2013-05-01 20:20:21

Added by:cegprakash
Date:2013-02-24
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64