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

hide comments
samarth1402: 2018-06-21 17:29:03

is there an editorial page for SPOJ problems?

ameyanator: 2018-06-11 15:25:31

Well i guess every problem has its edge cases

manishjha221: 2018-05-15 09:30:40

Last edit: 2018-05-15 09:31:16
zvirus: 2018-03-31 20:48:09

I am getting TLE using java any suggestion please
https://ideone.com/lRotIu

yatharth01: 2018-02-27 19:37:51

good question.! no next permutation needed .!!

vipulyadav150: 2018-02-27 19:37:45

Some comments mention use of next_permutation() function.....lol
Build an algo yourself man as I did it.....AC in SECOND GO!

prakash1108: 2018-02-12 19:02:00

Done with both.....with and without stl

kuchnahiaata: 2018-02-02 18:39:38

do not use STL if you want to learn something new out of this problem

bsoni_13: 2018-02-01 07:09:51

The algorithm link posted by @shauryauppal is really nice:)
http://www.nayuki.io/page/next-lexicographical-permutation-algorithm

damodhar47: 2018-01-24 11:20:22

where can i find editorial solution for this problem?


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