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
praveen123: 2013-05-02 06:48:14

@Orchid Majumder : try largest test. You can generate values randomly and check your how much time it takes on your pc.

Orchid: 2013-05-02 06:48:14

@praveen123, ID -8809360 ,getting TLE on judge no 3 ..any hint about any further optimization??

brahim: 2013-05-02 06:48:14

Hello, is it possible to have a hint on submission id 8756377?
thx
Found the bug.

Last edit: 2013-02-21 15:02:25
praveen123: 2013-05-02 06:48:14

@Anand Patil: try some numbers ending with zero

Last edit: 2013-02-19 20:44:05
Anand Patil: 2013-05-02 06:48:14

@praveen123: can u plz provide the hint on WA for code id - 8744696

praveen123: 2013-05-02 06:48:14

@ Nipun : Read constraints again.
I assure you that if your algorithm is correct , then there won't be any tricky test case as such.

praveen123: 2013-05-02 06:48:14

@ Aditya : It is expected to TLE

Nipun Poddar: 2013-05-02 06:48:14

what will be output for testcase-
45 2
45 3
45 45
0 1
0 0
according to me it should be-
\n
\n
\n
\n
0
please correct me if i am wrong !!

Last edit: 2013-02-17 09:00:47
Aditya Pande: 2013-05-02 06:48:14

my O(n^2) gives TLE

Last edit: 2013-02-17 06:18:01
Nnavneetsinha: 2013-05-02 06:48:14

@praveen123 Thanks a lot !! I got AC .Very nice problem.


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