Your friend Jeff Zebos has been trying to run his new online company, but it's not going very well. He's not getting a lot of sales on his website which he decided to call Azamon. His big problem, you think, is that he's not ranking high enough on the search engines. If only he could rename his products to have better names than his competitors, then he'll be at the top of the search results and will be a millionaire.

After doing some research, you find out that search engines only sort their results lexicographically. If your friend could rename his products to lexicographically smaller strings than his competitor's, then he'll be at the top of the rankings!

To make your strategy less obvious to his competitors, you decide to swap no more than two letters of the product names.

Please help Jeff to find improved names for his products that are lexicographically smaller than his competitor's!

Given the string $s$ representing Jeff's product name and the string $c$ representing his competitor's product name, find a way to swap at most one pair of characters in $s$ (that is, find two distinct indices $i$ and $j$ and swap $s_i$ and $s_j$) such that the resulting new name becomes strictly lexicographically smaller than $c$, or determine that it is impossible.

Note: String $a$ is strictly lexicographically smaller than string $b$ if and only if one of the following holds:  $a$ is a proper prefix of $b$, that is, $a$ is a prefix of $b$ such that $a \neq b$;  There exists an integer $1 \le i \le \min{(|a|, |b|)}$ such that $a_i < b_i$ and $a_j = b_j$ for $1 \le j < i$. 


-----Input-----

The first line of input contains a single integer $t$ ($1 \le t \le 1500$) denoting the number of test cases. The next lines contain descriptions of the test cases.

Each test case consists of a single line containing two space-separated strings $s$ and $c$ ($2 \le |s| \le 5000, 1 \le |c| \le 5000$). The strings $s$ and $c$ consists of uppercase English letters.

It is guaranteed that the sum of $|s|$ in the input is at most $5000$ and the sum of the $|c|$ in the input is at most $5000$.


-----Output-----

For each test case, output a single line containing a single string, which is either  the new name which is obtained after swapping no more than one pair of characters that is strictly lexicographically smaller than $c$. In case there are many possible such strings, you can output any of them;  three dashes (the string "---" without quotes) if it is impossible. 


-----Example-----
Input
3
AZAMON APPLE
AZAMON AAAAAAAAAAALIBABA
APPLE BANANA

Output
AMAZON
---
APPLE



-----Note-----

In the first test case, it is possible to swap the second and the fourth letters of the string and the resulting string "AMAZON" is lexicographically smaller than "APPLE".

It is impossible to improve the product's name in the second test case and satisfy all conditions.

In the third test case, it is possible not to swap a pair of characters. The name "APPLE" is lexicographically smaller than "BANANA". Note that there are other valid answers, e.g., "APPEL".

Difficulty: interview

Starter code:

Solutions:
import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

def solve():
    s,c = input().split()
    # i,jでjが複数あるとき
    n = len(s)
    for i in range(n-1):
        prev = s[i]
        pos = i
        for j in range(i+1, n):
            if s[j]<prev:
                prev = s[j]
                pos = j
            elif s[j] == prev:
                pos = j
        if prev == s[i]:
            continue
        t = list(s)
        t[i], t[pos] = prev, s[i]
        s = "".join(t)
        break
    if s<c:
        print(s)
    else:
        print("---")

t = int(input())
for i in range(t):
    solve()


import heapq
import math
from collections import *
from functools import reduce,cmp_to_key
import sys

input = sys.stdin.readline
M = mod = 10**9 + 7
def factors(n):return sorted(list(set(reduce(list.__add__,([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0)))))
def inv_mod(n):return pow(n, mod - 2, mod)

def li():return [int(i) for i in input().rstrip('\n').split(' ')]
def st():return input().rstrip('\n')
def val():return int(input())
def li2():return [i for i in input().rstrip('\n').split(' ')]


n = val()
for _ in range(n):
    s1,s2 = li2()
    fin = sorted(s1)

    if fin[0]>s2[0]:
        print('---')
        continue
    for i in range(len(s1)):
        if s1[i] != fin[i]:
            for j in range(len(s1)-1,-1,-1):
                if s1[j] == fin[i]:
                    s1 = list(s1)
                    s1[j] = s1[i]
                    s1[i] = fin[i]
                    s1 = ''.join(s1)
                    break
            break
    print('---' if s1 >= s2 else s1)


def main():
    TT = int(input())
    for _ in range(TT):
        w, t = input().strip().split(' ')
        w = list(w)

        sf = [len(w) - 1 for _ in range(len(w))]
        for i in range(len(w) - 2, -1, -1):
            if w[i] < w[sf[i+1]]:
                sf[i] = i
            else:
                sf[i] = sf[i + 1]

        for i in range(len(w)):
            if sf[i] != i and w[sf[i]] != w[i]:
                w[i], w[sf[i]] = w[sf[i]], w[i]
                break
        w = ''.join(w)
        if w < t:
            print(w)
        else:
            print('---')


def __starting_point():
    main()
__starting_point()

q=int(input())
for i in range(q):
    ok=[x for x in input().split()]
    r=ok[0]
    s=ok[1]
    w = [(ord(r[i])) for i in range(len(r))]
    w.sort()
    w=[chr(w[i]) for i in range(len(r))]
    first=True
    at=-1
    for j in range(len(r)):
        if w[j]!=r[j]:
            first=False
            at=j
            break
    if first==False:
        t=r[::-1].find(w[at])
        r=r[:at]+w[at]+r[at+1:len(r)-1-t]+r[at]+r[len(r)-t:]
    if r<s:
        print(r)
    else:
        print("---")

def gets(a):
    i = 0
    a = list(a)
    b = [0]*100
    
    for j in a:
        b[ord(j)-ord('A')]+=1
    
    r = -1
    t = -1
    while(b[i]==0 and i<26):
        i+=1
        
    for k in range(0,len(a)):
        if r==-1 and (ord(a[k]) - ord('A'))== i:
            b[i]-=1
            while(b[i]==0 and i<26):
                i+=1
        elif r==-1:
            t = k
            r = 0
        elif ord(a[k]) - ord('A') == i:
            r = k
    
    if r!=-1 and t!=-1:
        a[t] , a[r] = a[r] , a[t]
    return ''.join(a)

for _ in range(int(input())):
    a,b = input().split()
    a = gets(a)
    if a<b:
        print(a)
    else:
        print("---")

for _ in range(int(input())):
    a, b = input().split()
    a = list(a)
    for i in range(len(a)-1):
        j = min((i for i in range(i+1, len(a))), key=lambda x: (a[x], -x))
        if a[i] > a[j]:
            a[i], a[j] = a[j], a[i]
            break
        
    a = ''.join(a)
    if a < b:
        print(a)
    else:
        print('---')
            


import math

def better(a, b):
    for i in range(min(len(a), len(b))):
        if ord(a[i]) < ord(b[i]):
            return True
        elif ord(a[i]) > ord(b[i]):
            return False
    return len(a) < len(b)

def optimize(a):
    occ = [0] * 26
    for i in range(len(a)):
        occ[ord(a[i]) - ord('A')] += 1
    p1 = -1
    p2 = -1
    t = 0
    for i in range(len(a)):
        if p1 < 0:
            occ[ord(a[i]) - ord('A')] -= 1
            for j in range(ord(a[i]) - ord('A')):
                if occ[j] > 0:
                    p1 = i
                    t = j
                    break
        else:
            if ord(a[i]) - ord('A') == t:
                p2 = i

    if p1 >= 0 and p2 >= 0:
        return a[:p1] + a[p2] + a[p1+1:p2] + a[p1] + a[p2+1:]
    return a

def main():
    t = int(input())
    for i in range(t):
        line = str(input())
        p = line.split()
        mine = p[0]
        yours = p[1]
        new = optimize(mine)
        if better(new, yours):
            print(new)
        else:
            print('---')

def __starting_point():
    main()

__starting_point()

for _ in range(int(input())):
    a,c=input().split()
    a=list(a)
    b=sorted(a)
    if a!=b:
        for i,x in enumerate(b):
            if a[i]!=x:
                tmp=a[i]
                a[i]=x
                break
        for i in range(len(a)-1,-1,-1):
            if a[i]==x:
                a[i]=tmp
                break
    a=''.join(a)
    
    if a<c:
        print(a)
    else:
        print('---')

import sys
input = sys.stdin.readline

Q = int(input())
Query = [list(map(str, input().rstrip().split())) for _ in range(Q)]

for S, T in Query:
    L = len(S)
    update = False
    A = list(S)
    for i in range(L-1):
        tmp = S[i]
        for j in range(i+1, L):
            if update and tmp == S[j]:
                ind = j
            if tmp > S[j]:
                tmp = S[j]
                update = True
                ind = j
        if update:
            A[ind] = S[i]
            A[i] = S[ind]
            break
    A_str = "".join(A)
    if A_str < T:
        print(A_str)
    else:
        print("---")        

from string import ascii_uppercase

a = ascii_uppercase
N = int(input())

for i in range(N):
    me, comp = input().split(' ')
    # Want to maximize the lexicographic swap
    best = ''.join(sorted(me))
    # print(best)

    mismatch = -1
    for index, pair in enumerate(zip(best, me)):
        i, j = pair
        if i != j:
            mismatch = index
            break
    
    if mismatch != -1:
        # Want to swap mismatch (index) with last occurence after mismatch
        swaploc = len(me) - me[mismatch+1:][::-1].find(best[mismatch]) - 1
        swap1 = me[:mismatch] + me[swaploc] + me[mismatch+1:swaploc] + me[mismatch] + me[swaploc+1:]
    else:
        swap1 = me
    if swap1 < comp:
        print(swap1)
    else:
        print('---')

n = int(input())
for i in range(n):
	s, t = list(map(str, input().split()))
	if len(s) == 1:
		if s < t:
			print (s)
		else:
			print ("---")
		continue
	mas = [['ZZ', -1]]
	for j in range(len(s) - 1, -1, -1):
		if mas[-1][0] > s[j]:
			mas.append([s[j], j])
		else:
			mas.append(mas[-1])
	mas = mas[::-1]
	#print (*mas)
	flag = True
	for j in range(len(s)):
		#print (j)
		if s[j] > mas[j][0]:
			s = s[:j] + mas[j][0] + s[j + 1:mas[j][1]] + s[j] + s[mas[j][1] + 1:]
			if (s >= t):
				print ("---")
			else:
				print (s)
			flag = False
			break
	if flag:
		if s < t:
			print (s)
		else:
			print ("---")


import sys
input = sys.stdin.readline

def getInt(): return int(input())
def getVars(): return list(map(int, input().split()))
def getList(): return list(map(int, input().split()))
def getStr(): return input().strip()

## -------------------------------

n = getInt()
for i in range(n):
    s, c = getStr().split()
    p = False
    for i in range(len(s)-1):
        ch = i
        for j in range(i+1,len(s)):
            if s[j] <= s[ch]:
                ch = j
        if s[ch] < s[i]:
            s = s[:i] + s[ch] + s[i+1:ch] + s[i] + s[ch+1:]
            break
    if s < c: print(s)
    else: print('---')