JNEXT - Just Next !!!

DevG likes too much fun to do with numbers. Once his friend Arya came and gave him a challenge, he gave DevG an array of digits which is forming a number currently (will be called as given number). DevG was challanged to find the just next greater number which can be formed using digits of given number. Now DevG needs your help to find that just next greater number and win the challenge.

Input

The first line have t number of test cases (1 <= t <= 100). In next 2*t lines for each test case first there is number n (1 <= n <= 1000000) which denotes the number of digits in given number and next line contains n digits of given number separated by space.

Output

Print the just next greater number if possible else print -1 in one line for each test case.

Note : There will be no test case which contains zero in starting digits of any given number.

Example

Input:
2
5
1 5 4 8 3
10
1 4 7 4 5 8 4 1 2 6

Output:
15834
1474584162

Added by:! include(L.ppt)
Date:2012-08-31
Time limit:1.297s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:MNNIT OPC 31-08-2012

hide comments
2020-05-14 11:04:25
I have run below test case and results are fine.
Still its giving wrong answer in SPOJ.
stdin
8
5
1 5 4 8 3
10
1 4 7 4 5 8 4 1 2 6
7
2 7 9 9 8 7 3
3
3 1 2
3
1 3 2
4
2 9 9 2
3
1 2 3
5
1 1 1 1 1

stdout
15834
1474584162
2837799
321
213
9229
132
-1

Someone please suggest any specific test case which i should run to check correctness of my code.
2020-05-08 14:00:26
use array and next_permuation. It will ac in 1 go. :)
2020-05-07 10:06:44
For those who are getting wrong answers try this test case
7
2 7 9 9 8 7 3
2020-04-30 14:42:28
my code works for the given test cases and some of my own, but i'm getting a WA here. HELP.
2020-04-30 10:47:11
TLEEEEEEE
2020-04-15 17:53:16
@sayal_hajare
1
5
16897

correct o/p: 16978
your code might print: 17896, 16987
2020-04-15 13:10:15
Easy one just use next permutation
2020-04-10 16:23:14
i found this question under topic heading stack. how do we solve it using stack?


Last edit: 2020-04-10 17:08:16
2020-03-27 11:51:06
answer wiil be -1 for cases like : 1,2,333,4444
2020-03-26 06:53:46
O(n) in java giving tle. Need to use faster ip/op?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.