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
saurav52:
20170826 21:58:49
Did without STL :) 

laxman2405:
20170726 14:27:16
Dont forget the case of 1. Costed me 1WA


cake_is_a_lie:
20170302 06:37:20
int I/O 0.13; char I/O 0.02 

loverboy:
20161231 06:13:21
did without STL and with STL next_permutation().


scorpion_ajay:
20161219 08:28:42
answer will be 1 for cases like : 5 4 3 2 1


michaelscof:
20161110 11:50:02
throw some light on cases where ans would be 1?spojtoolkit cant help me.. :( 

ani_geek9654:
20160821 12:37:13
AC IN 2 WUHUU 

Ray Brish Bhanu:
20160819 13:30:40
don't use spoj toolkit for this que. 

suraj_:
20160813 15:17:39
did without stl


mkfeuhrer:
20160617 00:00:35
too easy with stl:) 
Added by:  ! include(L.ppt) 
Date:  20120831 
Time limit:  1.297s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  MNNIT OPC 31082012 