MAX_NUM - finding maximum possible number

no tags 

Given a number n, Find out what max possible number you can make by deleting exactly k digits.

T : no of test cases <= 10^3

1 <= no of digits in n <= 10^5. (n might contain leading zeros)

0 <= k <= n

if value of n is equal to k. then just print a new line.

Input

T: no of test cases

T line follow

every line has

n , k

Output

max possible number

Example

Input:
2
1223 2
8756 2
Output:
23
87
Explanation:

Note that left to right order should be maintained. As in the example given answer is 23 not 32.


hide comments
Archangel: 2014-05-21 16:42:09

@praveen123 I want to know that what is the way to remove k digits? Can k digits be removed from anywhere at random or k consecutive digits are to be removed?
Like for n=313 and k=1 we have 31 if consecutive digits are to be removed but if digits are to be removed at random then answer would be 33.
Please clarify my doubt I am not getting it.

Gaara: 2014-01-31 14:28:25

yipee... AC on my first attempt :D

Meraj Ahmed: 2013-12-26 20:52:33

@praveen: could you please look into my solution, I am doing it in O(n) and still getting TLE for judge 3.

solution id: 10744381

Last edit: 2013-12-26 20:53:33
BA_AK: 2013-12-11 11:22:59

If the answer contains leaning zeros, should we print them or omit them?

Achmet ibn Rashid: 2013-10-25 19:05:44

AC on first try :-) easy problem.

achiever202: 2013-07-06 16:27:31

@praveen123

my solution seems fine, i hav tried lots of test cases, bt i am getting WA... please, where am i going wrong...??

my solution code is 9614439

darryl: 2013-06-15 05:30:37

@Rajarshi Saha its 045. Print all numbers that are not deleted in the same order as stated.

Rajarshi Saha: 2013-06-05 14:25:45

@praveen123 can you tell me what should be the output for 0045 1? Shall it be 005 or 045; not clear about this.

Ankur: 2013-06-01 15:15:24

Finally.. AC :)
Awesome problem !!

Aditya Bahuguna: 2013-06-01 12:50:16

This gave me immense joy!!!AC


Added by:praveen123
Date:2013-02-09
Time limit:0.407s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:general