Jack and Daniel are friends. Both of them like letters, especially uppercase ones. 

They are cutting uppercase letters from newspapers, and each one of them has his collection of letters stored in a stack. 

One beautiful day, Morgan visited Jack and Daniel. He saw their collections. He wondered what is the lexicographically minimal string made of those two collections. He can take a letter from a collection only when it is on the top of the stack.  Morgan wants to use all of the letters in their collections.  

As an example, assume Jack has collected $a=[A,C,A]$ and Daniel has $b=[B,C,F]$.  The example shows the top at index $\mbox{0}$ for each stack of letters. Assemble the string  as follows:  

Jack	Daniel	result
ACA	BCF
CA	BCF	A
CA	CF	AB
A	CF	ABC
A	CF	ABCA
    	F	ABCAC
    		ABCACF

Note the choice when there was a tie at CA and CF.

Function Description  

Complete the morganAndString function in the editor below.  

morganAndString has the following parameter(s):  

string a: Jack's letters, top at index $\mbox{0}$  
string b: Daniel's letters, top at index $\mbox{0}$  

Returns 

- string: the completed string  

Input Format

The first line contains the an integer $\boldsymbol{\boldsymbol{t}}$, the number of test cases.  

The next $\boldsymbol{\boldsymbol{t}}$ pairs of lines are as follows: 

- The first line contains string $\boldsymbol{a}$ 

- The second line contains string $\boldsymbol{b}$.  

Constraints

$1\leq T\leq5$  
$1\leq|a|,|b|\leq10^5$  
$\boldsymbol{\alpha}$ and $\boldsymbol{b}$ contain upper-case letters only, ascii[A-Z].

Sample Input
2
JACK
DANIEL
ABACABA
ABACABA

Sample Output
DAJACKNIEL
AABABACABACABA

Explanation

The first letters to choose from are J and D since they are at the top of the stack. D is chosen and the options now are J and A. A is chosen. Then the two stacks have J and N, so J is chosen. The current string is DA. Continue this way to the end to get the string.

Source: hackerrank | Difficulty: HARD
Tags: String algorithms


Solutions:
import io

def pick_smaller_char(s1, s2, idx1, idx2, len1, len2, i1, i2):
	if len1 <= idx1[0]:
		idx2[0] += 1
		return s2[idx2[0] - 1]
	if len2 <= idx2[0]:
		idx1[0] += 1
		return s1[idx1[0] - 1]
	if s1[idx1[0]] > s2[idx2[0]]:
		idx2[0] += 1
		return s2[idx2[0] - 1]
	elif s1[idx1[0]] < s2[idx2[0]]:
		idx1[0] += 1
		return s1[idx1[0] - 1]
	else:
		if i1[0] < idx1[0] or i2[0] < idx2[0]:
			i1[0] = idx1[0]
			i2[0] = idx2[0]
		else:
			pass
		while i1[0] < len1 and i2[0] < len2 and (s1[i1[0]] == s2[i2[0]]):
			i1[0] += 1
			i2[0] += 1
		if (i1[0] < len1 and i2[0] < len2) and s1[i1[0]] != s2[i2[0]]:
			if s1[i1[0]] > s2[i2[0]]:
				idx2[0] += 1
				return s2[idx2[0] - 1]
			elif s1[i1[0]] < s2[i2[0]]:
				idx1[0] += 1
				return s1[idx1[0] - 1]
		elif i1[0] < len1 and i2[0] >= len2:
			idx1[0] += 1
			return s1[idx1[0] - 1]
		elif i1[0] >= len1 and i2[0] < len2:
			idx2[0] += 1
			return s2[idx2[0] - 1]
		else:
			i1[0] = 0
			i2[0] = 0
			if len1 - idx1[0] > len2 - idx2[0]:
				idx1[0] += 1
				return s1[idx1[0] - 1]
			else:
				idx2[0] += 1
				return s2[idx2[0] - 1]

def main():
	trials = int(input())
	for trial in range(trials):
		word1 = input()
		word2 = input()
		word = io.StringIO()
		len1 = len(word1)
		len2 = len(word2)
		idx1 = [0]
		idx2 = [0]
		i1 = [0]
		i2 = [0]
		timeout = 0
		while len1 - idx1[0] > 0 or len2 - idx2[0] > 0:
			word.write(pick_smaller_char(word1, word2, idx1, idx2, len1, len2, i1, i2))
		print(word.getvalue())
		word.close()
main()


from collections import deque
for _ in range(int(input())):
	a = input() + '['
	b = input() + '['
	output = deque()
	for _ in range(len(a) + len(b) - 2):
		if a < b:
			output.append(a[0])
			a = a[1:]
		else:
			output.append(b[0])
			b = b[1:]
	print(''.join(output))


from collections import deque
from builtins import range
from builtins import input
for _ in range(int(input())):
	a = input() + '['
	b = input() + '['
	string = deque()
	while len(a) > 1 and len(b) > 1:
		if a < b:
			string.append(a[0])
			a = a[1:]
		else:
			string.append(b[0])
			b = b[1:]
	print(''.join(string) + a[:-1] + b[:-1])


from collections import deque

def minstring(a, b):
	result = deque()
	while len(a) > 1 and len(b) > 1:
		if a < b:
			result.append(a[0])
			a = a[1:]
		else:
			result.append(b[0])
			b = b[1:]
	return ''.join(result) + a[:-1] + b[:-1]
n = int(input())
for _ in range(n):
	a = input()
	b = input()
	print(minstring(a + ']', b + ']'))


def merge(A, B):
	(m, n) = (len(A), len(B))
	(i, j) = (0, 0)
	merged = []
	while i < m and j < n:
		if A[i] < B[j]:
			merged.append(A[i])
			i += 1
		elif A[i] > B[j]:
			merged.append(B[j])
			j += 1
		else:
			(ii, jj) = (i, j)
			c = A[ii]
			while ii < m and jj < n and (A[ii] == B[jj]):
				if A[ii] > c:
					merged.append(A[i:ii])
					merged.append(B[j:jj])
					i = ii
					j = jj
					c = A[ii]
				ii += 1
				jj += 1
			if ii == m:
				merged.append(B[j])
				j += 1
			elif jj == n:
				merged.append(A[i])
				i += 1
			elif A[ii] < B[jj]:
				merged.append(A[i])
				i += 1
			else:
				merged.append(B[j])
				j += 1
	return ''.join(merged) + A[i:] + B[j:]

def main():
	T = int(input())
	for _ in range(T):
		A = input()
		B = input()
		print(merge(A, B))
main()


t = int(input())
for _ in range(t):
	A = input()
	B = input()
	i = 0
	j = 0
	res = []
	while i < len(A) or j < len(B):
		if j >= len(B) or (i < len(A) and A[i] < B[j]):
			res.append(A[i])
			i += 1
		elif i >= len(A) or (j < len(B) and A[i] > B[j]):
			res.append(B[j])
			j += 1
		elif A[i] == B[j]:
			flag = True
			x = i
			y = j
			while x < len(A) and y < len(B) and flag:
				if A[x] < B[y]:
					res.append(A[i:x + 1])
					i = x + 1
					flag = False
				elif A[x] > B[y]:
					res.append(B[j:y + 1])
					j = y + 1
					flag = False
				x += 1
				y += 1
			if flag:
				if x == len(A):
					res.append(B[j])
					j += 1
				else:
					res.append(A[i])
					i += 1
	print(''.join(res))


import math
import sys
import string
from bisect import bisect
t = int(input())
while t:
	sa = input()
	sb = input()
	(i, j) = (0, 0)
	ans = ''
	while 1:
		if sa == '':
			ans += sb
			break
		if sb == '':
			ans += sa
			break
		if sa > sb:
			if len(sa) > len(sb) and sb == sa[:len(sb)]:
				if sa[len(sb)] > sb[0]:
					ans += sb[0]
					sb = sb[1:]
				else:
					ans += sa[0]
					sa = sa[1:]
			else:
				ans += sb[0]
				sb = sb[1:]
		elif len(sb) > len(sa) and sa == sb[:len(sa)]:
			if sb[len(sa)] > sa[0]:
				ans += sa[0]
				sa = sa[1:]
			else:
				ans += sb[0]
				sb = sb[1:]
		else:
			ans += sa[0]
			sa = sa[1:]
	print(ans)
	t -= 1


for t in range(int(input())):
	ans = ''
	s = input()
	t = input()
	for i in range(len(s + t)):
		if s + '~' < t + '~':
			ans += s[0]
			s = s[1:]
		else:
			ans += t[0]
			t = t[1:]
	print(ans)


from collections import deque
for _ in range(int(input())):
	a = input() + '['
	b = input() + '['
	output = deque()
	for _ in range(len(a) + len(b) - 2):
		if a < b:
			output.append(a[0])
			a = a[1:]
		else:
			output.append(b[0])
			b = b[1:]
	print(''.join(output))


t = int(input())
for _ in range(t):
	string1 = input()
	string2 = input()
	string = []
	i = 0
	j = 0
	len1 = len(string1)
	len2 = len(string2)
	while i < len1 and j < len2:
		x = string1[i]
		y = string2[j]
		if x == y:
			p = string1[i:]
			q = string2[j:]
			l1 = len(p)
			l2 = len(q)
			if l1 > l2:
				q = q + 'z'
			else:
				p = p + 'z'
			if p < q:
				string.append(string1[i])
				i = i + 1
			else:
				string.append(string2[j])
				j = j + 1
		if x < y:
			string.append(string1[i])
			i = i + 1
		if x > y:
			string.append(string2[j])
			j = j + 1
	while i < len1:
		string.append(string1[i])
		i = i + 1
	while j < len2:
		string.append(string2[j])
		j = j + 1
	print(''.join(string))


def getLexicographicallySmallestWord(word1, word2):
	lexicographicallySmallestWord = ''
	word1Index = 0
	word2Index = 0
	numberOfAvoidedLetters = 0
	while word1Index != len(word1) or word2Index != len(word2):
		if word1Index == len(word1):
			lexicographicallySmallestWord += word2[word2Index:]
			word2Index = len(word2)
		elif word2Index == len(word2):
			lexicographicallySmallestWord += word1[word1Index:]
			word1Index = len(word1)
		elif word1[word1Index] < word2[word2Index] or word1[word1Index:] + '_' < word2[word2Index:] + '_':
			lexicographicallySmallestWord += word1[word1Index]
			word1Index += 1
		else:
			lexicographicallySmallestWord += word2[word2Index]
			word2Index += 1
	return lexicographicallySmallestWord
for i in range(int(input())):
	print(getLexicographicallySmallestWord(input(), input()))


max_c = chr(ord('Z') + 1)

def lowest(a, b):
	len_a = len(a)
	len_b = len(b)
	a += max_c
	b += max_c
	i = j = 0
	while i < len_a or j < len_b:
		if a[i:] < b[j:]:
			yield a[i]
			i += 1
		else:
			yield b[j]
			j += 1
n_tests = int(input())
for t in range(n_tests):
	a = input()
	b = input()
	print(''.join(lowest(a, b)))


T = int(input())

def fill(L, a, b, v):
	for i in range(a, b + 1):
		L[i] = v
for t in range(T):
	A = list(input())
	B = list(input())
	result = []
	AA = [0] * len(A)
	BB = [0] * len(B)
	a = b = 0
	for i in range(len(A + B)):
		if a < len(A) and b < len(B):
			if A[a] > B[b]:
				result.append(B[b])
				b += 1
			elif A[a] < B[b]:
				result.append(A[a])
				a += 1
			elif A[a] == B[b] and AA[a] == BB[b]:
				limit = min(len(A) - a, len(B) - b)
				found = ''
				findex = 0
				for j in range(limit):
					if A[a + j] > B[b + j]:
						result.append(B[b])
						b += 1
						found = 'b'
						findex = j
						break
					elif A[a + j] < B[b + j]:
						result.append(A[a])
						a += 1
						found = 'a'
						findex = j
						break
				if found == '':
					if len(A) - a > len(B) - b:
						result.append(A[a])
						a += 1
					else:
						result.append(B[b])
						b += 1
				elif found == 'a':
					fill(AA, a - 1, a + j - 1, 1)
				elif found == 'b':
					fill(BB, b - 1, b + j - 1, 1)
			elif A[a] == B[b] and AA[a] == 1:
				result.append(A[a])
				a += 1
			elif A[a] == B[b] and BB[b] == 1:
				result.append(B[b])
				b += 1
		elif a >= len(A):
			result.append(B[b])
			b += 1
		elif b >= len(B):
			result.append(A[a])
			a += 1
	print(''.join(result))


T = int(input())
for i in range(T):
	A = input()
	B = input()
	S = ''
	while A or B:
		N = min(len(A), len(B))
		if A and (not B):
			S = S + A[0]
			A = A[1:]
		elif B and (not A):
			S = S + B[0]
			B = B[1:]
		elif A[0:N] < B[0:N]:
			S = S + A[0]
			A = A[1:]
		elif B[0:N] < A[0:N]:
			S = S + B[0]
			B = B[1:]
		elif len(B) > N:
			S = S + B[0]
			B = B[1:]
		else:
			S = S + A[0]
			A = A[1:]
	print(S)


for _ in range(int(input())):
	a = input()
	b = input()
	a += 'z'
	b += 'z'
	la = len(a)
	lb = len(b)
	(i, j) = (0, 0)
	lex = ''
	while i < la and j < lb:
		if a[i:] < b[j:]:
			lex += a[i]
			i += 1
			tmp = a[i - 1]
			while i < la and a[i] == tmp:
				lex += a[i]
				i += 1
		else:
			lex += b[j]
			j += 1
	for k in range(i, la):
		lex += a[k]
	for k in range(j, lb):
		lex += b[k]
	print(lex[:-2])


for t in range(int(input())):
	(A, B) = (input() + 'z', input() + 'z')
	out = ''
	while A != 'z' and B != 'z':
		if A <= B:
			out = out + A[0]
			A = A[1:]
		else:
			out = out + B[0]
			B = B[1:]
	print(out + A[:-1] + B[:-1])


def findIncrease(s, stop):
	v = 0
	for i in range(stop - 1):
		if s[i] < s[i + 1]:
			return i + 1
	return stop

def aIsBetter(a, b):
	stop = min(len(a), len(b))
	for i in range(stop):
		if a[i] < b[i]:
			return (True, i)
		if b[i] < a[i]:
			return (False, i)
	if len(a) > len(b):
		return (True, stop)
	return (False, stop)

def breakTie(res, a, b):
	(t, stop) = aIsBetter(a, b)
	if t:
		i = findIncrease(a, stop)
		res += a[:i]
		a = a[i:]
		return (res, a, b)
	else:
		i = findIncrease(b, stop)
		res += b[:i]
		b = b[i:]
		return (res, a, b)
n = int(input())
for problem in range(n):
	a = input().upper()
	b = input().upper()
	res = ''
	while len(a) > 0 and len(b) > 0:
		if ord(a[0]) < ord(b[0]):
			res += a[0]
			a = a[1:]
		elif ord(a[0]) > ord(b[0]):
			res += b[0]
			b = b[1:]
		else:
			(res, a, b) = breakTie(res, a, b)
	res += a + b
	print(res)


from collections import deque
for _ in range(int(input())):
	a = input() + '['
	b = input() + '['
	output = deque()
	for _ in range(len(a) + len(b) - 2):
		if a < b:
			output.append(a[0])
			a = a[1:]
		else:
			output.append(b[0])
			b = b[1:]
	print(''.join(output))


def getLMS(s1, s2):
	(i, j) = (0, 0)
	a = []
	while i < len(s1) and j < len(s2):
		if s1[i] < s2[j]:
			a.append(s1[i])
			i += 1
		elif s2[j] < s1[i]:
			a.append(s2[j])
			j += 1
		else:
			(x, y) = (i, j)
			c = s1[i]
			while x < len(s1) and y < len(s2):
				if s1[x] != s2[y]:
					break
				elif s1[x] > c:
					a.append(s1[i:x])
					a.append(s2[j:y])
					(i, j) = (x, y)
					c = s1[x]
				x += 1
				y += 1
			if x == len(s1):
				a.append(s2[j])
				j += 1
			elif y == len(s2):
				a.append(s1[i])
				i += 1
			elif s1[x] < s2[y]:
				a.append(s1[i])
				i += 1
			else:
				a.append(s2[j])
				j += 1
	a.append(s1[i:])
	a.append(s2[j:])
	for k in a:
		print(k, end='')
	print()
t = int(input())
for i in range(t):
	string1 = input()
	string2 = input()
	getLMS(string1, string2)


k = int(input())
for i in range(k):
	A = input()
	B = input()
	s = ''
	while A and B:
		if A[0] != B[0]:
			if A[0] < B[0]:
				s += A[0]
				A = A[1:]
			else:
				s += B[0]
				B = B[1:]
		elif A == B:
			s += A[0]
			A = A[1:]
		else:
			m = min(len(A), len(B))
			if A[:m] == B[:m]:
				if len(A) > len(B):
					s += A[0]
					A = A[1:]
				else:
					s += B[0]
					B = B[1:]
			else:
				for i in range(m):
					if A[0:i + 1] != B[0:i + 1]:
						if i < 3:
							if A[0:i + 1] < B[0:i + 1]:
								s += A[0]
								A = A[1:]
							else:
								s += B[0]
								B = B[1:]
							break
						else:
							if A[0:i + 1] < B[0:i + 1]:
								s += A[0:i]
								A = A[i:]
							else:
								s += B[0:i]
								B = B[i:]
							break
	if len(A) != 0:
		s += A
	if len(B) != 0:
		s += B
	print(s)


def find_minimal_string(a, b):
	a += 'z'
	b += 'z'
	result = ''
	(i, j) = (0, 0)
	while i + 1 < len(a) and j + 1 < len(b):
		if a[i:] <= b[j:]:
			result += a[i]
			i += 1
		else:
			result += b[j]
			j += 1
	result += a[i:len(a) - 1] + b[j:len(b) - 1]
	return result
T = int(input().strip())
for t in range(T):
	a = input().strip()
	b = input().strip()
	result = find_minimal_string(a, b)
	print(result)


def morgan(s1, s2):
	(i, j) = (0, 0)
	s1 += 'a'
	s2 += 'a'
	out = ''
	while s1[i] != 'a' or s2[j] != 'a':
		if s1[i] < s2[j]:
			out += s1[i]
			i += 1
		elif s1[i] > s2[j]:
			out += s2[j]
			j += 1
		else:
			decider = s1[i]
			(m, n) = (i, j)
			hid = 0
			hid_good = True
			while s1[m] == s2[n]:
				if s1[m] == 'a':
					break
				if s1[m] > decider:
					break
				if s1[m] != decider:
					hid_good = False
				elif hid_good:
					hid += 1
				m += 1
				n += 1
			if s1[m] > s2[n]:
				out += s2[j:j + hid]
				j += hid
			else:
				out += s1[i:i + hid]
				i += hid
	return out
ncases = int(input())
for i in range(ncases):
	(s1, s2) = (input().strip() for _ in range(2))
	out = morgan(s1, s2)
	print(out)


n = int(input())
for _ in range(n):
	a = input() + 'a'
	b = input() + 'a'
	(i, j, res, m, n) = (0, 0, [], len(a), len(b))
	while i < m and j < n:
		if a[i] < b[j]:
			res.append(a[i])
			i += 1
		elif a[i] > b[j]:
			res.append(b[j])
			j += 1
		elif a[i + 1:] < b[j + 1:]:
			res.append(a[i])
			i += 1
		else:
			res.append(b[j])
			j += 1
	if i == m:
		res.extend(b[j:])
	else:
		res.extend(a[i:])
	res.pop()
	res.pop()
	print(''.join(res))


def minLex(strA, strB):
	ans = ''
	strA += 'a'
	strB += 'a'
	while strA and strB:
		if strA <= strB:
			ans += strA[0]
			strA = strA[1:]
		else:
			ans += strB[0]
			strB = strB[1:]
	return (ans + strA + strB)[:-2]
t = int(input().strip())
for t_ in range(t):
	strA = input().strip()
	strB = input().strip()
	print(minLex(strA, strB))


def better_stack(stack1, stack2, ps1, ps2):
	for (i, j) in zip(range(ps1, len(stack1)), range(ps2, len(stack2))):
		if stack1[i] < stack2[j]:
			return (1, i)
		elif stack2[j] < stack1[i]:
			return (2, j)
	return (1, ps1)

def lexmin(string1, string2):
	ret = ''
	stack1 = [ord(c) for c in string1] + [ord('Z') + 1]
	stack2 = [ord(c) for c in string2] + [ord('Z') + 1]
	ps1 = 0
	ps2 = 0
	sid = -1
	ptr = -1
	while ps1 < len(stack1) - 1 and ps2 < len(stack2) - 1:
		if sid == -1:
			(sid, ptr) = better_stack(stack1, stack2, ps1, ps2)
		if sid == 1:
			ret += chr(stack1[ps1])
			ps1 += 1
			if ps1 > ptr:
				sid = -1
		else:
			ret += chr(stack2[ps2])
			ps2 += 1
			if ps2 > ptr:
				sid = -1
	if ps1 < len(stack1) - 1:
		ret += ''.join([chr(c) for c in stack1[ps1:len(stack1) - 1]])
	if ps2 < len(stack2) - 1:
		ret += ''.join([chr(c) for c in stack2[ps2:len(stack2) - 1]])
	return ret
ncases = int(input())
for nc in range(ncases):
	string1 = input().strip()
	string2 = input().strip()
	print(lexmin(string1, string2))


t = int(input())
for _ in range(t):
	a = input() + 'z'
	b = input() + 'z'
	i = 0
	j = 0
	sol = []
	while i < len(a) and j < len(b):
		if a[i] < b[j]:
			sol.append(a[i])
			i += 1
			continue
		if a[i] > b[j]:
			sol.append(b[j])
			j += 1
			continue
		skip = 0
		while i + skip < len(a) and j + skip < len(b) and (a[i + skip] == b[j + skip]) and (a[i + skip] == a[i]):
			skip += 1
		sol.extend([a[i] for _ in range(skip)])
		if i + skip >= len(a):
			j += skip
			continue
		elif j + skip >= len(b) or a[i + skip:] < b[j + skip:]:
			i += skip
			continue
		else:
			j += skip
			continue
	if i < len(a):
		sol.extend(a[i:])
	else:
		sol.extend(b[j:])
	sol = sol[:-2]
	print(''.join(sol))


import sys
data = sys.stdin.read().split('\n')
testCount = int(data[0])
inputTest = []
if testCount >= 1 and testCount <= 5:
	for i in range(1, testCount * 2, 2):
		inputTest.append(data[i])
		inputTest.append(data[i + 1])
	for i in range(0, len(inputTest), 2):
		j = 0
		k = 0
		str = ''
		while j < len(inputTest[i]) and k < len(inputTest[i + 1]):
			if inputTest[i][j] == inputTest[i + 1][k]:
				x = j + 1
				y = k + 1
				if x == len(inputTest[i]):
					str = str + inputTest[i + 1][k]
					k = k + 1
					continue
				elif y == len(inputTest[i + 1]):
					str = str + inputTest[i][j]
					j = j + 1
					continue
				while x < len(inputTest[i]) and y < len(inputTest[i + 1]):
					if inputTest[i][x] == inputTest[i + 1][y]:
						x = x + 1
						y = y + 1
						if x == len(inputTest[i]):
							str = str + inputTest[i + 1][k]
							k = k + 1
							break
						elif y == len(inputTest[i + 1]):
							str = str + inputTest[i][j]
							j = j + 1
							break
					elif inputTest[i][x] < inputTest[i + 1][y]:
						str = str + inputTest[i][j:x]
						j = x
						break
					else:
						str = str + inputTest[i + 1][k:y]
						k = y
						break
			elif inputTest[i][j] < inputTest[i + 1][k]:
				str = str + inputTest[i][j]
				j = j + 1
			else:
				str = str + inputTest[i + 1][k]
				k = k + 1
		if k < len(inputTest[i + 1]):
			str = str + inputTest[i + 1][k:]
		if j < len(inputTest[i]):
			str = str + inputTest[i][j:]
		print(str)


__author__ = 'abdujabbor'

def find_lex_min_string(s1, s2):
	result = ''
	i = 0
	j = 0
	len1 = len(s1)
	len2 = len(s2)
	while i < len1 and j < len2:
		if s1[i] == s2[j]:
			x = i
			y = j
			a = s1[i]
			while x < len1 and y < len2:
				if s1[x] != s2[y]:
					break
				elif a < s1[x]:
					result += s1[i:x]
					result += s2[j:y]
					i = x
					j = y
					a = s1[x]
				x += 1
				y += 1
			if x == len1:
				result += s2[j]
				j += 1
			elif y == len2:
				result += s1[i]
				i += 1
			elif s1[x] < s2[y]:
				result += s1[i]
				i += 1
			else:
				result += s2[j]
				j += 1
		elif s1[i] < s2[j]:
			result += s1[i]
			i += 1
		elif s1[i] > s2[j]:
			result += s2[j]
			j += 1
	if i < len(s1):
		result += s1[i:]
	if j < len(s2):
		result += s2[j:]
	return result
t = int(input())
for i in range(t):
	print(find_lex_min_string(input(), input()))


T = int(input())
for t in range(T):
	A = input() + 'z'
	B = input() + 'z'
	output = ''
	while len(A) > 1 and len(B) > 1:
		if A > B:
			output += B[0]
			B = B[1:]
		else:
			output += A[0]
			A = A[1:]
	if len(A) > 1:
		output += A[:-1]
	else:
		output += B[:-1]
	print(output)


def solve(j, d):
	ij = 0
	id = 0
	mj = len(j)
	md = len(d)
	ans = []
	while True:
		o = 1
		if j[ij] < d[id]:
			isjack = True
		elif j[ij] > d[id]:
			isjack = False
		elif ij + 1 == mj:
			isjack = False
		elif id + 1 == md:
			isjack = True
		else:
			while True:
				if ij + o == mj:
					isjack = False
					break
				elif id + o == md:
					isjack = True
					break
				if j[ij + o] < d[id + o]:
					isjack = True
					break
				elif j[ij + o] > d[id + o]:
					isjack = False
					break
				elif j[ij + o - 1] < j[ij + o]:
					o2 = o + 1
					while ij + o2 < mj and id + o2 < md and (j[ij + o2] == d[id + o2]):
						o2 += 1
					if ij + o2 == mj:
						isjack = False
					elif id + o2 == md:
						isjack = True
					else:
						isjack = j[ij + o2] < d[id + o2]
					break
				o += 1
		if isjack:
			ans.append(j[ij:ij + o])
			ij += o
			if ij == mj:
				return ''.join(ans) + d[id:]
		else:
			ans.append(d[id:id + o])
			id += o
			if id == md:
				return ''.join(ans) + j[ij:]
for _ in range(int(input())):
	j = input()
	d = input()
	print(solve(j, d))


def findSmallest(string1, string2):
	result = []
	string1Index = 0
	string2Index = 0
	appendString1 = 0
	forwardAppendCount = 0
	different = False
	useString1 = False
	useString2 = False
	while string1Index < len(string1) or string2Index < len(string2):
		if string1Index < len(string1) and string2Index < len(string2):
			useString2 = False
			if appendString1 == 1 or appendString1 == 2:
				for i in range(forwardAppendCount):
					if appendString1 == 1:
						result.append(string1[string1Index])
						string1Index += 1
					else:
						result.append(string2[string2Index])
						string2Index += 1
				forwardAppendCount = 0
				appendString1 = 0
			elif string1[string1Index] < string2[string2Index]:
				result.append(string1[string1Index])
				string1Index += 1
			elif string2[string2Index] < string1[string1Index]:
				result.append(string2[string2Index])
				string2Index += 1
			else:
				different = True
				tempIndex1 = string1Index
				tempIndex2 = string2Index
				prevChar = string1[tempIndex1]
				while string1[tempIndex1] == string2[tempIndex2]:
					tempIndex1 += 1
					tempIndex2 += 1
					if tempIndex1 >= len(string1) and tempIndex2 >= len(string2):
						tempIndex1 -= 1
						tempIndex2 -= 1
						break
					elif tempIndex1 >= len(string1):
						useString2 = True
						break
					elif tempIndex2 >= len(string2):
						useString1 = True
						break
					if prevChar == string1[tempIndex1] and different:
						forwardAppendCount += 1
					else:
						different = False
				if useString1 or useString2:
					if useString1:
						appendString1 = 1
						result.append(string1[string1Index])
						string1Index += 1
					else:
						appendString1 = 2
						result.append(string2[string2Index])
						string2Index += 1
				elif string1[tempIndex1] == string2[tempIndex2]:
					appendString1 = 1
					result.append(string1[string1Index])
					string1Index += 1
				elif string1[tempIndex1] < string2[tempIndex2]:
					appendString1 = 1
					result.append(string1[string1Index])
					string1Index += 1
				else:
					appendString1 = 2
					result.append(string2[string2Index])
					string2Index += 1
		elif string1Index < len(string1):
			result.append(string1[string1Index])
			string1Index += 1
		else:
			result.append(string2[string2Index])
			string2Index += 1
	return ''.join(result)
n = int(input())
for i in range(n):
	string1 = input()
	string2 = input()
	my_answer = findSmallest(string1, string2)
	print(my_answer)


import sys
ts = int(input().strip())
for t in range(0, ts):
	s1 = input().strip() + 'z'
	s2 = input().strip() + 'z'
	n1 = len(s1)
	n2 = len(s2)
	n = n1 + n2
	i1 = 0
	i2 = 0
	s = []
	for j in range(0, n):
		if i2 == n2:
			s.append(s1[i1])
			i1 += 1
		elif i1 == n1:
			s.append(s2[i2])
			i2 += 1
		elif ord(s1[i1]) < ord(s2[i2]):
			s.append(s1[i1])
			i1 += 1
		elif ord(s1[i1]) > ord(s2[i2]):
			s.append(s2[i2])
			i2 += 1
		elif s1[i1:] < s2[i2:]:
			s.append(s1[i1])
			i1 += 1
		else:
			s.append(s2[i2])
			i2 += 1
	print(''.join(s)[:-2])


T = int(input())
for t in range(T):
	jack = input()
	daniel = input()
	i = 0
	j = 0
	result = ''
	cache = {}
	while True:
		if i >= len(jack) and j >= len(daniel):
			break
		forward = 0
		maxForward = -1
		lastJackValue = 'a'
		if (i, j) in cache:
			shouldUseJack = cache[i, j]
		else:
			while True:
				if i + forward >= len(jack):
					if j + forward > len(daniel):
						break
					jackValue = 'a'
				else:
					jackValue = jack[i + forward]
				if j + forward >= len(daniel):
					danielValue = 'a'
				else:
					danielValue = daniel[j + forward]
				if jackValue < danielValue:
					shouldUseJack = True
					break
				if jackValue > danielValue:
					shouldUseJack = False
					break
				if jackValue > jack[i]:
					shouldUseJack = True
					break
				if maxForward < 0 and jackValue == jack[i] and (jackValue > lastJackValue):
					maxForward = forward
				lastJackValue = jackValue
				forward += 1
			if maxForward > 0:
				forward = maxForward
			if shouldUseJack:
				for ii in range(i + 1, i + forward - 1):
					cache[ii, j] = shouldUseJack
			else:
				for jj in range(j + 1, j + forward - 1):
					cache[i, jj] = shouldUseJack
		if shouldUseJack:
			result += jack[i]
			i += 1
		else:
			result += daniel[j]
			j += 1
	print(result)


def shortest_smallest(A, B, a, b):
	len_A = len(A)
	len_B = len(B)
	cant_0 = 1
	lett_0 = A[a]
	cant_a = 1
	lett_A = A[a]
	cant_b = 1
	lett_B = B[b]
	while True:
		if a + cant_a < len_A:
			if A[a] == A[a + cant_a]:
				cant_a += 1
			else:
				lett_A = A[a + cant_a]
		else:
			while b + cant_b < len_B and B[b] == B[b + cant_b]:
				cant_b += 1
			return ('B', cant_b)
		if b + cant_b < len_B:
			if B[b] == B[b + cant_b]:
				cant_b += 1
			else:
				lett_B = B[b + cant_b]
		else:
			while a + cant_a < len_A and A[a] == A[a + cant_a]:
				cant_a += 1
			return ('A', cant_a)
		if A[a] != A[a + cant_a] or B[b] != B[b + cant_b]:
			break
		else:
			cant_0 += 1
	if lett_0 < lett_A and lett_0 < lett_B:
		return ('AB', cant_0)
	if lett_A == lett_B:
		if A[a + cant_0:] < B[b + cant_0:]:
			return ('A', cant_0)
		else:
			return ('B', cant_0)
	if lett_A < lett_B:
		return ('A', cant_a)
	return ('B', cant_b)

def resolv_lex(A, B, a=0, b=0, result=''):
	len_A = len(A)
	len_B = len(B)
	while True:
		if a < len_A and b < len_B:
			if A[a:] < B[b:]:
				result += A[a]
				a += 1
			else:
				result += B[b]
				b += 1
		elif a < len_A:
			result += A[a]
			a += 1
		elif b < len_B:
			result += B[b]
			b += 1
		else:
			break
	return result
T = int(input().strip())
for t in range(T):
	A = input().strip()
	B = input().strip()
	print(resolv_lex(A + 'z', B + 'z')[:-2])


for _ in range(int(input())):
	res = ''
	A = input()
	B = input()
	minimum = min(len(A), len(B))
	A += 'z'
	B += 'z'
	la = len(A)
	lb = len(B)
	a = 0
	b = 0
	while a < la and b < lb:
		if A[a:] <= B[b:]:
			res = res + A[a]
			a = a + 1
		else:
			res = res + B[b]
			b = b + 1
	if b < lb:
		res = res + B[b:]
	else:
		res = res + A[a:]
	print(res[:-2])


n = int(input().strip())
for i in range(n):
	t = input().strip()
	s = input().strip()
	t += 'z'
	s += 'z'
	string = ''
	(i, j) = (0, 0)
	while i < len(t) - 1 or j < len(s) - 1:
		if t[i:] < s[j:]:
			string += t[i]
			i += 1
		else:
			string += s[j]
			j += 1
	print((string + t[i:] + s[j:])[:-2])


numberOfTests = int(input())
for test in range(numberOfTests):
	finalString = ''
	string1 = list(input().strip())
	string2 = list(input().strip())
	string1.reverse()
	string2.reverse()
	while string1 or string2:
		if not string1:
			finalString += string2.pop()
		elif not string2:
			finalString += string1.pop()
		elif string1[-1] < string2[-1]:
			finalString += string1.pop()
		elif string2[-1] < string1[-1]:
			finalString += string2.pop()
		else:
			stringToPop = None
			i = 1
			while string1 or string2:
				if i >= len(string1) and i >= len(string2):
					i = 1
					stringToPop = 1
					break
				if i >= len(string1):
					stringToPop = 2
					break
				elif i >= len(string2):
					stringToPop = 1
					break
				elif string1[-1 - i] < string2[-1 - i]:
					stringToPop = 1
					break
				elif string2[-1 - i] < string1[-1 - i]:
					stringToPop = 2
					break
				i += 1
			for ii in range(i):
				if stringToPop == 1:
					finalString += string1.pop()
				else:
					finalString += string2.pop()
	print(finalString)


for _ in range(int(input())):
	a = input() + '['
	b = input() + '['
	lA = len(a)
	lB = len(b)
	(i, j) = (0, 0)
	res = ''
	while i < lA and j < lB:
		if a[i:] < b[j:]:
			res += a[i]
			i += 1
		else:
			res += b[j]
			j += 1
	for k in range(i, lA):
		res += a[k]
	for k in range(j, lB):
		res += b[k]
	print(res[:-2])


def test():
	a = input().strip()
	b = input().strip()
	a = a + 'z'
	b = b + 'z'
	index_a = 0
	index_b = 0
	lex_min = []
	while index_a < len(a) or index_b < len(b):
		if a[index_a:] <= b[index_b:] and index_a < len(a):
			lex_min.append(a[index_a])
			index_a += 1
		else:
			lex_min.append(b[index_b])
			index_b += 1
	lex_min.pop()
	lex_min.pop()
	print(''.join(lex_min))
test_cases = input().strip()
test_cases = int(test_cases)
for t in range(test_cases):
	test()


for test in range(int(input())):
	(a, b) = (input() + '~' for line in range(2))
	i = j = 0
	while not a[i] == b[j] == '~':
		if a[i:] < b[j:]:
			print(end=a[i])
			i += 1
		else:
			print(end=b[j])
			j += 1
	print()


from heapq import heappush, heappop

def main():
	T = int(input())
	for _ in range(T):
		A = input()
		B = input()
		C = []
		h = []
		heappush(h, A)
		heappush(h, B)
		while h:
			S = heappop(h)
			C.append(S[0])
			if S[1] != '[':
				heappush(h, S[1:] + '[')
		print(''.join(C))
main()


import string

def cmp(A, B):
	return (A > B) - (A < B)
t = int(input())
while t > 0:
	A = input()
	B = input()
	A = A + 'z'
	B = B + 'z'
	a = len(A)
	b = len(B)
	while (a >= 1) & (b > 1) | (b >= 1) & (a > 1):
		x = cmp(A, B)
		if x <= 0:
			print(A[0], end='')
			A = A[1:]
			a -= 1
		else:
			print(B[0], end='')
			B = B[1:]
			b -= 1
	t -= 1
	print('\n', end='')


t = input().strip()
t = int(t)
for _ in range(t):
	a = input().strip()
	b = input().strip()
	a += chr(ord('Z') + 1)
	b += chr(ord('Z') + 1)
	new_str = ''
	(i, j) = (0, 0)
	while i < len(a) and j < len(b):
		if a[i] < b[j]:
			new_str += a[i]
			i += 1
		elif a[i] > b[j]:
			new_str += b[j]
			j += 1
		elif a[i:] <= b[j:]:
			new_str += a[i]
			i += 1
		else:
			new_str += b[j]
			j += 1
	while i < len(a):
		new_str += a[i]
		i += 1
	while j < len(b):
		new_str += b[j]
		j += 1
	print(new_str[:len(new_str) - 2])


n = int(input())
iA = 0
iB = 0
while n > 0:
	sA = str(input()) + 'a'
	sB = str(input()) + 'a'
	iA = 0
	iB = 0
	while iA + iB < len(sA) + len(sB) - 2:
		if iA < len(sA) and iB < len(sB):
			if sA[iA:] <= sB[iB:] and sA[iA] != 'a':
				print(sA[iA], end='')
				iA += 1
			elif sB[iB] != 'a':
				print(sB[iB], end='')
				iB += 1
		else:
			if iA < len(sA):
				print(sA[iA:len(sA) - 1])
			else:
				print(sB[iB:len(sB) - 1])
			break
	n -= 1
	print('')


def two_way_merge(s1, s2):
	i = 0
	j = 0
	temp = []
	s1 = s1 + chr(200)
	s2 = s2 + chr(200)
	while i < len(s1) - 1 or j < len(s2) - 1:
		if s1[i] == s2[j]:
			k = i + 1
			p = j + 1
			ch = s1[i]
			foundBeforeEnd = False
			while k < len(s1) - 1 and p < len(s2) - 1:
				s1Next = s1[k]
				s2Next = s2[p]
				if s1Next == s2Next:
					if s1Next > ch:
						temp.extend(list(s1[i:k]))
						temp.extend(list(s2[j:p]))
						i = k
						j = p
						foundBeforeEnd = True
						break
					else:
						k += 1
						p += 1
				else:
					if min(s1[k], s2[p]) > ch:
						temp.extend(list(s1[i:k]))
						temp.extend(list(s2[j:p]))
						i = k
						j = p
					elif min(s1[k], s2[p]) == s1[k]:
						temp.extend(list(s1[i:k]))
						i = k
					elif min(s1[k], s2[p]) == s2[p]:
						temp.extend(list(s2[j:p]))
						j = p
					foundBeforeEnd = True
					break
			if not foundBeforeEnd:
				if k == len(s1) - 1 and p == len(s2) - 1:
					temp.extend(s1[i])
					i += 1
				elif k == len(s1) - 1 and p != len(s2) - 1:
					if s2[p] > ch:
						temp.extend(list(s1[i:k]))
						temp.extend(list(s2[j:p]))
						i = k
						j = p
					elif s2[p] <= ch:
						temp.extend(list(s2[j:p]))
						j = p
				elif k != len(s1) - 1 and p == len(s2) - 1:
					if s1[k] > ch:
						temp.extend(list(s1[i:k]))
						temp.extend(list(s2[j:p]))
						i = k
						j = p
					elif s1[k] <= ch:
						temp.extend(list(s1[i:k]))
						i = k
		elif s1[i] < s2[j]:
			temp.append(s1[i])
			i += 1
		else:
			temp.append(s2[j])
			j += 1
	return ''.join(temp)
numTests = int(input())
l = []
(jack, daniel) = (None, None)
for i in range(1, numTests * 2 + 1):
	if i % 2 == 1:
		jack = input()
	else:
		daniel = input()
		l.append((jack, daniel))
for item in l:
	print(two_way_merge(item[0], item[1]))


T = int(input())
for k in range(T):
	A = list(input())
	B = list(input())
	R = []
	(i, j) = (0, 0)
	aLen = len(A)
	bLen = len(B)
	while i < aLen and j < bLen:
		if A[i] < B[j]:
			R.append(A[i])
			i = i + 1
		elif A[i] > B[j]:
			R.append(B[j])
			j = j + 1
		else:
			x = i + 1
			y = j + 1
			flag = False
			while x < aLen and y < bLen:
				if A[x] < B[y]:
					R.append(A[i])
					i = i + 1
					flag = True
					break
				elif B[y] < A[x]:
					R.append(B[j])
					j = j + 1
					flag = True
					break
				if A[x] > A[i]:
					for h in range(i, x):
						R.append(A[h])
						i = i + 1
					for h in range(j, y):
						R.append(B[h])
						j = j + 1
					flag = True
					break
				x = x + 1
				y = y + 1
			if flag == False and x == aLen and (y == bLen):
				R.append(A[i])
				i = i + 1
			elif flag == False and x == aLen:
				if B[y] <= B[j]:
					for h in range(j, y):
						R.append(B[h])
						j = j + 1
				else:
					print(A[i:x])
					for h in range(i, x):
						R.append(A[h])
						i = i + 1
					break
			elif flag == False and y == bLen:
				if A[x] <= A[i]:
					for h in range(i, x):
						R.append(A[h])
						i = i + 1
				else:
					for h in range(j, y):
						R.append(B[h])
						j = j + 1
					break
	while i < aLen:
		R.append(A[i])
		i = i + 1
	while j < bLen:
		R.append(B[j])
		j = j + 1
	for char in R:
		print(char, end='')
	print()


import sys

def infer(a, b):
	if len(a) <= len(b):
		if a == b[:len(a)]:
			return False
		else:
			return a <= b
	elif b == a[:len(b)]:
		return True
	else:
		return a <= b
t = int(input().strip())
for a0 in range(t):
	m1 = input().strip()
	m2 = input().strip()
	i = 0
	j = 0
	while m1 != '' and m2 != '':
		if infer(m1, m2):
			print(m1[0], end='')
			m1 = m1[1:]
		else:
			print(m2[0], end='')
			m2 = m2[1:]
	if m2 == '':
		print(m1)
	elif m1 == '':
		print(m2)


import sys

def solve(s1, s2):
	s1 += '|'
	s2 += '|'
	i1 = i2 = 0
	r = ''
	while i1 < len(s1) - 1 and i2 < len(s2) - 1:
		if s1[i1:] < s2[i2:]:
			r += s1[i1]
			i1 += 1
		else:
			r += s2[i2]
			i2 += 1
	r += s1[i1:-1] + s2[i2:-1]
	return r
rl = lambda : sys.stdin.readline().strip()
n = int(rl())
for i in range(0, n):
	s1 = rl()
	s2 = rl()
	print(solve(s1, s2))


T = int(input())
for t in range(T):
	left = input() + 'z'
	right = input() + 'z'
	i = 0
	j = 0
	res = ''
	while i < len(left) and j < len(right):
		if left[i:] <= right[j:]:
			res += left[i]
			i += 1
		else:
			res += right[j]
			j += 1
	for a in range(i, len(left)):
		res += left[a]
	for b in range(j, len(right)):
		res += right[b]
	print(res[0:len(res) - 2])


T = int(input())
for _ in range(T):
	(a, b) = (input() + 'a', input() + 'a')
	result = ''
	while len(a) > 1 or len(b) > 1:
		if len(b) == 1 or (len(a) > 1 and a < b):
			result += a[0]
			a = a[1:]
		else:
			result += b[0]
			b = b[1:]
	print(result)


t = int(input().strip())

def combine_str(a, b):
	la = len(a)
	lb = len(b)
	result = ''
	while la > 0 and lb > 0:
		if a[0] > b[0]:
			result += b[0]
			b = b[1:]
			lb -= 1
		elif a[0] < b[0]:
			result += a[0]
			a = a[1:]
			la -= 1
		else:
			fl = True
			for i in range(1, min(la, lb)):
				if a[i] > b[i]:
					result += b[:i]
					b = b[i:]
					lb -= i
					fl = False
					break
				elif a[i] < b[i]:
					result += a[:i]
					a = a[i:]
					la -= i
					fl = False
					break
			if fl:
				if lb > la:
					result += b[0]
					b = b[1:]
					lb -= 1
				else:
					result += a[0]
					a = a[1:]
					la -= 1
	if la > 0:
		result += a
	elif lb > 0:
		result += b
	print(result)
for _ in range(t):
	a = input().strip()
	b = input().strip()
	combine_str(a, b)


import sys

def morganString():
	word1 = input().strip()
	word2 = input().strip()
	index1 = 0
	index2 = 0
	len1 = len(word1)
	len2 = len(word2)
	offset = 0
	charList = []
	loop = True
	while index1 < len1 and index2 < len2:
		if word1[index1] < word2[index2]:
			charList.append(word1[index1])
			index1 += 1
		elif word1[index1] > word2[index2]:
			charList.append(word2[index2])
			index2 += 1
		else:
			offset = 1
			pattern_offset = 0
			less = False
			while index1 + offset < len1 and index2 + offset < len2 and (word1[index1 + offset] == word2[index2 + offset]):
				if pattern_offset > 0 and offset - pattern_offset < pattern_offset and (word1[index1 + offset] < word1[index1 + (offset - pattern_offset)]):
					less = True
				if word1[index1 + offset] > word1[index1] or (not less and pattern_offset > 0 and (offset - pattern_offset < pattern_offset) and (word1[index1 + offset] > word1[index1 + (offset - pattern_offset)])):
					ofc = pattern_offset if pattern_offset > 0 else offset
					ofc2 = ofc
					while ofc > 0:
						charList.append(word1[index1])
						ofc -= 1
						index1 += 1
					while ofc2 > 0:
						charList.append(word2[index2])
						ofc2 -= 1
						index2 += 1
					offset = 0
					break
				if word1[index1 + offset] == word1[index1] and word1[index1 + offset - 1] < word1[index1 + offset] and (offset - pattern_offset >= pattern_offset):
					pattern_offset = offset
					less = False
				offset += 1
			if offset <= 0:
				continue
			if index1 + offset < len1 and index2 + offset < len2:
				if word1[index1 + offset] < word2[index2 + offset]:
					while offset > 0:
						charList.append(word1[index1])
						index1 += 1
						offset -= 1
				else:
					while offset > 0:
						charList.append(word2[index2])
						index2 += 1
						offset -= 1
			elif index1 + offset >= len1 and index2 + offset >= len2:
				ofc = pattern_offset if pattern_offset > 0 else offset
				while ofc > 0:
					charList.append(word1[index1])
					index1 += 1
					ofc -= 1
			else:
				ofc = pattern_offset if pattern_offset > 0 else offset
				if index1 + offset >= len1:
					while ofc > 0:
						charList.append(word2[index2])
						index2 += 1
						ofc -= 1
				else:
					while ofc > 0:
						charList.append(word1[index1])
						index1 += 1
						ofc -= 1
	while index1 < len1:
		charList.append(word1[index1])
		index1 += 1
	while index2 < len2:
		charList.append(word2[index2])
		index2 += 1
	sys.stdout.write(str.join('', charList) + '\n')
count = int(input().strip())
while count > 0:
	morganString()
	count -= 1


for _ in range(int(input())):
	(a, b) = (input() + '|', input() + '|')
	result = ''
	while len(a) > 1 and len(b) > 1:
		if a <= b:
			result += a[0]
			a = a[1:]
		else:
			result += b[0]
			b = b[1:]
	result += a[:-1] + b[:-1]
	print(result)


import sys
tc = int(input())
for t in range(tc):
	a = input() + 'z'
	b = input() + 'z'
	i = j = 0
	result = []
	while i < len(a) and j < len(b):
		if a[i:] < b[j:]:
			result.append(a[i])
			i += 1
		else:
			result.append(b[j])
			j += 1
	result = result[:-1]
	if i < len(a):
		result += a[i:-1]
	if j < len(b):
		result += b[j:-1]
	print(''.join(result))


def morgan(first, second):
	i = 0
	j = 0
	c = ''
	while i != len(first) - 1 and j != len(second) - 1:
		if first[i:-1] < second[j:-1]:
			c = c + first[i]
			i += 1
		else:
			c = c + second[j]
			j += 1
	c = c + first[i:-1] + second[j:-1]
	print(c[0:-2])
tc = int(input())
for i in range(tc):
	first = input().strip() + 'z' + '|'
	second = input().strip() + 'z' + '|'
	morgan(first, second)


t = int(input())
while t > 0:
	a = input()
	b = input()
	a += 'z'
	b += 'z'
	c = ''
	n = len(a) + len(b) - 2
	for i in range(n):
		if a <= b:
			c += a[0]
			a = a[1:]
		else:
			c += b[0]
			b = b[1:]
	print(c)
	t -= 1


from collections import deque
for _ in range(int(input())):
	a = input() + '['
	b = input() + '['
	output = deque()
	for _ in range(len(a) + len(b) - 2):
		if a < b:
			output.append(a[0])
			a = a[1:]
		else:
			output.append(b[0])
			b = b[1:]
	print(''.join(output))


from collections import deque

def compare_first_non_substring(inp_s, sub_s):
	assert len(sub_s) < len(inp_s)
	cmp_res = None
	inp_str = ''.join((str(e) for e in inp_s))
	sub_str = ''.join((str(e) for e in sub_s))
	sub_len = len(sub_str)
	last_found_idx = inp_str.find(sub_str)
	assert last_found_idx == 0
	next_idx = last_found_idx
	while True:
		next_idx = inp_str.find(sub_str, next_idx + sub_len)
		if next_idx == last_found_idx + sub_len:
			last_found_idx = next_idx
		else:
			break
	first_non_substr_idx = last_found_idx + sub_len
	if first_non_substr_idx == len(inp_str):
		cmp_res = 0
	elif sub_str < inp_str[first_non_substr_idx:]:
		cmp_res = -1
	else:
		cmp_res = 1
	return (cmp_res, first_non_substr_idx)

def take_descending_matches(a, b, m):
	assert a[0] == b[0]
	(short_str, long_str) = (None, None)
	if len(a) != len(b):
		(short_str, long_str) = (a, b) if len(a) < len(b) else (b, a)
	cur_min = a[0]
	mismatch_idx = None
	first_increasing_idx = None
	i = 0
	for (ca, cb) in zip(a, b):
		if ca != cb:
			mismatch_idx = i
			break
		if first_increasing_idx is None:
			if ca > cur_min:
				first_increasing_idx = i
			else:
				cur_min = ca
		i += 1
	if mismatch_idx is not None:
		assert ca != cb
		min_str = a if ca < cb else b
		last_peak = min_str[0]
		while min_str and min_str[0] <= last_peak:
			m.append(min_str.popleft())
			if min_str and min_str[0] < last_peak:
				last_peak = min_str[0]
	elif short_str:
		(substr_cmp_result, first_non_substr_idx) = compare_first_non_substring(long_str, short_str)
		if substr_cmp_result == 1:
			for __ in range(first_non_substr_idx):
				m.append(long_str.popleft())
		else:
			m.extend(short_str)
			short_str.clear()
	elif first_increasing_idx is not None:
		for __ in range(first_increasing_idx):
			m.append(a.popleft())
	else:
		m.extend(a)
		a.clear()
		m.extend(b)
		b.clear()

def index_of_next_peak(a, b):
	(ca, cb) = (a[0], b[0])
	cur_max = ca
	ret_idx = 0
	assert ca == cb
	i = 0
	for (ca, cb) in zip(a, b):
		if ca != cb or ca < cur_max:
			break
		if ca > cur_max:
			cur_max = ca
			ret_idx = i
		i += 1
	if ca == cb and i == max([len(a), len(b)]):
		return i
	return ret_idx

def lexicographical_min(a, b):
	a = deque(a)
	b = deque(b)
	m = []
	while a and b:
		(ca, cb) = (a[0], b[0])
		if ca < cb:
			a.popleft()
			m.append(ca)
		elif cb < ca:
			b.popleft()
			m.append(cb)
		else:
			first_peak_idx = index_of_next_peak(a, b)
			if first_peak_idx > 0:
				for __ in range(first_peak_idx):
					m.append(a.popleft())
					m.append(b.popleft())
			else:
				take_descending_matches(a, b, m)
	if not a:
		m.extend(b)
	else:
		m.extend(a)
	return ''.join(m)
n = int(input().strip())
for __ in range(n):
	a = input().strip()
	b = input().strip()
	print(lexicographical_min(a, b))


from itertools import islice
for t in range(int(input())):
	(s1, s2) = (input() + 'z', input() + 'z')
	(i1, i2) = (0, 0)
	while i1 < len(s1) - 1 or i2 < len(s2) - 1:
		if i1 < len(s1) - 1 and (not i2 < len(s2) - 1):
			print(s1[i1:-1])
			break
		elif i2 < len(s2) - 1 and (not i1 < len(s1) - 1):
			print(s2[i2:-1])
			break
		elif s1[i1:] < s2[i2:]:
			print(s1[i1], end='')
			i1 += 1
		else:
			print(s2[i2], end='')
			i2 += 1


import sys

def syntes(jack, daniel):
	result = ''
	j = 0
	d = 0
	while j < len(jack) and d < len(daniel):
		if jack[j:] + '{' < daniel[d:] + '{':
			result += jack[j]
			j += 1
			if j == len(jack):
				result += daniel[d:]
				d = len(daniel)
		else:
			result += daniel[d]
			d += 1
			if d == len(daniel):
				result += jack[j:]
				j = len(jack)
	return result
n = int(input().strip())
for _ in range(n):
	jack = input().strip()
	daniel = input().strip()
	print(syntes(jack, daniel))


for _ in range(int(input())):
	a = input() + '['
	b = input() + '['
	output = ''
	for _ in range(len(a) + len(b) - 2):
		if a < b:
			output += a[0]
			a = a[1:]
		else:
			output += b[0]
			b = b[1:]
	print(output)


t = int(input())
for _ in range(t):
	(str1, str2) = (input(), input())
	(l1, l2) = (len(str1), len(str2))
	(i, j) = (0, 0)
	res = ''
	preferred = None
	while i < l1 or j < l2:
		if i < l1 and j < l2:
			if ord(str1[i]) < ord(str2[j]):
				res += str1[i]
				i += 1
				preferred = None
			elif ord(str1[i]) > ord(str2[j]):
				res += str2[j]
				j += 1
				preferred = None
			elif preferred is not None:
				if preferred == 0:
					res += str1[i]
					i += 1
				else:
					res += str2[j]
					j += 1
			else:
				for k in range(max(l1, l2)):
					if i + k < l1 and j + k < l2:
						if ord(str1[i + k]) < ord(str2[j + k]):
							preferred = 0
							break
						elif ord(str1[i + k]) > ord(str2[j + k]):
							preferred = 1
							break
						elif i + k == l1 - 1 and j + k == l2 - 1:
							preferred = 1
					elif i + k < l1:
						preferred = 0
						break
					else:
						preferred = 1
						break
		elif i < len(str1):
			res += str1[i]
			i += 1
			preferred = 0
		else:
			res += str2[j]
			j += 1
			preferred = 1
	print(res)


for _ in range(int(input())):
	a = input()
	b = input()
	a += 'z'
	b += 'z'
	la = len(a)
	lb = len(b)
	(i, j) = (0, 0)
	min = ''
	while i < la and j < lb:
		if a[i:] < b[j:]:
			min += a[i]
			i += 1
		else:
			min += b[j]
			j += 1
	for k in range(i, la):
		min += a[k]
	for k in range(j, lb):
		min += b[k]
	print(min[:-2])


t = int(input())
for i in range(t):
	a = input()
	b = input()
	lena = len(a)
	lenb = len(b)
	a += 'z'
	b += 'z'
	while len(a) > 1 or len(b) > 1:
		if len(a) > 1 and len(b) > 1:
			if a[0] < b[0]:
				print(a[0], end='')
				a = a[1:]
			elif a[0] > b[0]:
				print(b[0], end='')
				b = b[1:]
			elif a < b:
				print(a[0], end='')
				a = a[1:]
			else:
				print(b[0], end='')
				b = b[1:]
		elif len(a) > 1:
			print(a[:-1], end='')
			a = ''
		else:
			print(b[:-1], end='')
			b = ''
	print()


T = int(input())
while T > 0:
	T -= 1
	a = input() + 'a'
	b = input() + 'a'
	c = len(a) + len(b) - 2
	output = ''
	for _ in range(c):
		if a < b:
			output += a[0]
			a = a[1:]
		else:
			output += b[0]
			b = b[1:]
	print(output)


def lms(first, second):
	flag = 0
	result = ''
	(p1, p2) = (0, 0)
	(first, second) = (first + chr(ord('Z') + 1), second + chr(ord('Z') + 1))
	(l1, l2) = (len(first), len(second))
	while p1 < l1 and p2 < l2:
		if first[p1] < second[p2]:
			(result, p1, flag) = (result + first[p1], p1 + 1, 0)
		elif second[p2] < first[p1]:
			(result, p2, flag) = (result + second[p2], p2 + 1, 0)
		elif flag == -1:
			(result, p1) = (result + first[p1], p1 + 1)
		elif flag == 1:
			(result, p2) = (result + second[p2], p2 + 1)
		else:
			(pp1, pp2) = (p1, p2)
			while pp1 < l1 and pp2 < l2 and (first[pp1] == second[pp2]):
				(pp1, pp2) = (pp1 + 1, pp2 + 1)
			if pp1 >= l1 or first[pp1] < second[pp2]:
				(result, p1, flag) = (result + first[p1], p1 + 1, -1)
			elif pp2 >= l2 or first[pp1] > second[pp2]:
				(result, p2, flag) = (result + second[p2], p2 + 1, 1)
	if p1 < l1 - 1:
		result += first[p1:-2]
	if p2 < l2 - 1:
		result += second[p2:-2]
	return result[:-1]
for _ in range(int(input())):
	print(lms(input(), input()))


def morgan(s1, s2, i1=0, i2=0):
	return ''.join(revalpha(mergemax(revalpha(s1), revalpha(s2))))

def revalpha(s):
	subfrom = ord('A') + ord('Z')
	return [chr(subfrom - ord(c)) for c in ''.join(s)]

def mergemax(s1, s2):
	if len(s1) == 0:
		return s2
	elif len(s2) == 0:
		return s1
	i1 = i2 = 0
	(c1, c2) = (s1[0], s2[0])
	s1.append(chr(0))
	s2.append(chr(1))
	ans = []
	while True:
		if c1 > c2:
			ans.append(c1)
			i1 += 1
			c1 = s1[i1]
		elif c1 < c2:
			if c2 == chr(1):
				return ans
			ans.append(c2)
			i2 += 1
			c2 = s2[i2]
		else:
			(i1, i2, newseq) = resolvetie(s1, i1, s2, i2)
			c1 = s1[i1]
			c2 = s2[i2]
			ans += newseq

def resolvetie(s1, i1, s2, i2):
	cstart = s1[i1]
	assert cstart == s2[i2]
	(i1, chunk1) = chunkify(s1, i1)
	(i2, chunk2) = chunkify(s2, i2)
	ans = mergemax(chunk1, chunk2)
	cnt = 0
	while s1[i1] == cstart:
		cnt += 1
		i1 += 1
	while s2[i2] == cstart:
		cnt += 1
		i2 += 1
	if cnt > 0:
		ans.append(cstart * cnt)
	return (i1, i2, ans)

def chunkify(s, i):
	cstart = s[i]
	ans = []
	while True:
		chunkstart = i
		i += 1
		while s[i] == cstart:
			i += 1
		if s[i] < cstart:
			return (chunkstart, ans)
		while s[i] > cstart:
			i += 1
		ans.append(''.join(s[chunkstart:i]))
		if s[i] < cstart:
			return (i, ans)

def main():
	ncases = int(input())
	for case in range(ncases):
		s1 = input().strip()
		s2 = input().strip()
		print(morgan(s1, s2))
main()


import sys

def func(s1, s2):
	(s1, s2) = (list(s1), list(s2))
	(n1, n2) = (len(s1), len(s2))

	def compcost(i1, i2):
		while 1:
			if i1 == n1:
				return 2
			elif i2 == n2:
				return 1
			elif s1[i1] < s2[i2]:
				return 1
			elif s1[i1] > s2[i2]:
				return 2
			i1 += 1
			i2 += 1

	def internal(i1, i2):
		ls = []
		cache = None
		keep_cache = False
		while 1:
			if not keep_cache:
				cache = None
			keep_cache = False
			if i1 == n1:
				ls.extend(s2[i2:])
				return ls
			elif i2 == n2:
				ls.extend(s1[i1:])
				return ls
			elif s1[i1] < s2[i2]:
				ls.append(s1[i1])
				i1 += 1
			elif s1[i1] > s2[i2]:
				ls.append(s2[i2])
				i2 += 1
			elif i1 + 1 == n1:
				ls.append(s2[i2])
				i2 += 1
			elif i2 + 1 == n2:
				ls.append(s1[i1])
				i1 += 1
			elif cache == 1:
				keep_cache = True
				ls.append(s1[i1])
				i1 += 1
			elif cache == 2:
				keep_cache = True
				ls.append(s2[i2])
				i2 += 1
			elif compcost(i1 + 1, i2 + 1) == 1:
				cache = 1
				keep_cache = True
				ls.append(s1[i1])
				i1 += 1
			else:
				cache = 2
				keep_cache = True
				ls.append(s2[i2])
				i2 += 1
	return ''.join(internal(0, 0))
sys.setrecursionlimit(100010)
t = int(input())
for _ in range(t):
	print(func(input(), input()))


import re
for _ in range(int(input())):
	a = input().strip()
	b = input().strip()
	d = len(a) + len(b)
	s = ''
	while a and b:
		if a[0] < b[0]:
			s += a[0]
			a = a[1:]
		elif a[0] > b[0]:
			s += b[0]
			b = b[1:]
		else:
			la = len(a)
			lb = len(b)
			ml = min(la, lb)
			if a[:ml] == b[:ml]:
				if len(a) >= len(b):
					s += a[0]
					a = a[1:]
				else:
					s += b[0]
					b = b[1:]
			else:
				for i in range(ml):
					if a[i] < b[i]:
						s += a[:i + 1]
						a = a[i + 1:]
						break
					elif a[i] > b[i]:
						s += b[:i + 1]
						b = b[i + 1:]
						break
	print(s + a + b)


def firstHigherLetter(input_str):
	check = input_str[0]
	idx = 0
	for x in input_str:
		if x > check:
			return idx
		idx += 1
	return -1

def firstEqual(a, b, ans):
	min_length = min(len(a), len(b))
	a_min = a[:min_length]
	b_min = b[:min_length]
	old_a = a[0]
	old_b = b[0]
	finished = False
	for x in range(min_length):
		if a[x] == b[x] and a[x] > old_a and (b[x] > old_b):
			ans += a[0:x]
			a = a[x:]
			finished = True
			break
		elif a[x] == b[x] and a[x] > old_a and (b[x] <= old_b):
			ans += b[0:x + 1]
			b = b[x + 1:]
			finished = True
			break
		elif a[x] == b[x] and a[x] <= old_a and (b[x] > old_b):
			ans += a[0:x + 1]
			a = a[x + 1:]
			finished = True
			break
		elif a[x] != b[x]:
			if a[x] > b[x]:
				ans += b[0:x]
				b = b[x:]
				finished = True
				break
			else:
				ans += a[0:x]
				a = a[x:]
				finished = True
				break
		else:
			pass
	if finished == False:
		if len(a) > len(b):
			ans += a[0]
			a = a[1:]
		else:
			ans += b[0]
			b = b[1:]
	return (a, b, ans)

def morgan(a, b):
	ans = ''
	while len(a) > 0 or len(b) > 0:
		if len(a) == 0:
			ans += b
			break
		if len(b) == 0:
			ans += a
			break
		if a[0] > b[0]:
			ans += b[0]
			b = b[1:]
		elif a[0] < b[0]:
			ans += a[0]
			a = a[1:]
		else:
			(a, b, ans) = firstEqual(a, b, ans)
	return ans
cases = int(input())
for i in range(cases):
	a = input()
	b = input()
	print(morgan(a, b))


def main():
	a = input() + 'z'
	b = input() + 'z'
	i = 0
	j = 0
	la = len(a) - 1
	lb = len(b) - 1
	c = []
	while i < la and j < lb:
		if a[i] < b[j]:
			print(a[i], end='')
			i += 1
		elif b[j] < a[i]:
			print(b[j], end='')
			j += 1
		elif a[i + 1:] < b[j + 1:]:
			print(a[i], end='')
			i += 1
		else:
			print(b[j], end='')
			j += 1
	print(a[i:-1] + b[j:-1])
n = int(input())
for _ in range(n):
	main()


def get_lex_string(A, B):
	res = []
	if len(B) == 0:
		return A
	if len(A) == 0:
		return B
	i = 0
	j = 0
	while i < len(A) and j < len(B):
		if A[i] < B[j]:
			res.append(A[i])
			i += 1
		elif A[i] == B[j]:
			if A[i + 1:] + 'z' < B[j + 1:] + 'z':
				res.append(A[i])
				i += 1
			else:
				res.append(B[j])
				j += 1
		else:
			res.append(B[j])
			j += 1
	res += A[i:] + B[j:]
	return ''.join(res)
T = int(input())
for _ in range(T):
	A = input().strip()
	B = input().strip()
	print(get_lex_string(A, B))


cases = int(input())
while cases > 0:
	cases -= 1
	s1 = input()
	s2 = input()
	s1 += '['
	s2 += '['
	l1 = len(s1)
	l2 = len(s2)
	ans = ''
	for i in range(l1 + l2 - 2):
		if s1 < s2:
			ans += s1[0]
			s1 = s1[1:]
		else:
			ans += s2[0]
			s2 = s2[1:]
	print(ans)


n = int(input())
for _ in range(n):
	A = input()
	B = input()
	ans = ''
	(i, j) = (0, 0)
	current = 0
	while True:
		if i == len(A) and j == len(B):
			break
		if i == len(A):
			ans += B[j]
			j += 1
			continue
		if j == len(B):
			ans += A[i]
			i += 1
			continue
		if ord(A[i]) > ord(B[j]):
			ans += B[j]
			j += 1
			current = 0
		elif ord(A[i]) == ord(B[j]):
			i_temp = i
			j_temp = j
			if current == 0:
				while A[i_temp] == B[j_temp]:
					if i_temp == len(A) - 1 or j_temp == len(B) - 1:
						break
					i_temp += 1
					j_temp += 1
			if ord(A[i_temp]) > ord(B[j_temp]) or current == 2:
				ans += B[j]
				j += 1
				current = 2
			elif ord(A[i_temp]) < ord(B[j_temp]) or current == 1:
				ans += A[i]
				i += 1
				current = 1
			elif len(A) - i_temp < len(B) - j_temp:
				ans += B[j]
				j += 1
			else:
				ans += A[i]
				i += 1
		else:
			ans += A[i]
			i += 1
			current = 0
	print(ans)


def resol(si, sj):
	(si, sj) = (si + 'z', sj + 'z')
	(i, j) = (0, 0)
	(li, lj) = (len(si), len(sj))
	res = ''
	while i < li or j < lj:
		(ci, cj) = (i, j)
		while ci < li and cj < lj and (si[ci] == sj[cj]):
			ci += 1
			cj += 1
		if ci != i:
			if ci < li and cj < lj:
				if si[ci] < sj[cj]:
					res += si[i:ci]
					i = ci
				else:
					res += sj[j:cj]
					j = cj
				continue
		if i < li and j < lj:
			if si[i] < sj[j]:
				res += si[i]
				i += 1
			else:
				res += sj[j]
				j += 1
		elif i == li:
			res += sj[j]
			j += 1
		else:
			res += si[i]
			i += 1
	return res[:-2]
import sys
n = int(sys.stdin.readline())
for i in range(n):
	a = sys.stdin.readline().strip()
	b = sys.stdin.readline().strip()
	print(resol(a, b))


import string

def cmp(A, B):
	return (A > B) - (A < B)
t = int(input())
while t > 0:
	A = input()
	B = input()
	A = A + 'z'
	B = B + 'z'
	a = len(A)
	b = len(B)
	while (a >= 1) & (b > 1) | (b >= 1) & (a > 1):
		x = cmp(A, B)
		if x <= 0:
			print(A[0], end='')
			A = A[1:]
			a -= 1
		else:
			print(B[0], end='')
			B = B[1:]
			b -= 1
	t -= 1
	print('\n', end='')


n = int(input().strip())
for i in range(n):
	A = input().strip()
	B = input().strip()
	ABStacks = [list(A[::-1]), list(B[::-1])]

	def GetMatch(Stacks):
		StackLens = [len(m) for m in Stacks]
		MinLen = min(StackLens)
		if Stacks[0][-1] == Stacks[1][-1]:
			MatchRange = [-1, -1]
			i = -1
			for i in range(-2, -(MinLen + 1), -1):
				if Stacks[0][i] == Stacks[1][i]:
					MatchRange[1] -= 1
				else:
					i += 1
					break
		else:
			MatchRange = [None, None]
			i = 0
		if StackLens[0] + i == 0:
			Priority = 1
		elif StackLens[1] + i == 0:
			Priority = 0
		elif Stacks[0][i - 1] < Stacks[1][i - 1]:
			Priority = 0
		else:
			Priority = 1
		return ([[m for m in MatchRange] for m1 in [0, 0]], Priority)
	(MatchRange, Priority) = GetMatch(ABStacks)

	def MRLen(MatchRange):
		if MatchRange[0][0] != None:
			return MatchRange[0][0] - MatchRange[0][1] + 1
		else:
			return -1

	def UpdateMatchRange(MatchRange, AltInd):
		if MatchRange[0][0] != None:
			MatchRange[AltInd][1] += 1
			NewLenMinusOne = MatchRange[AltInd][0] - MatchRange[AltInd][1]
			MatchRange[1 - AltInd][0] = MatchRange[1 - AltInd][1] + NewLenMinusOne
			ShiftAll = -1 - max([MatchRange[0][0], MatchRange[1][0]])
			if ShiftAll > 0:
				MatchRange = [[MatchRange[m2][m1] + ShiftAll for m1 in [0, 1]] for m2 in [0, 1]]
		return MatchRange
	OutStr = ''
	MatchRangeActive = [[MatchRange[m2][m1] for m1 in [0, 1]] for m2 in [0, 1]]
	PriorityActive = Priority
	MatchRangeInActive = [[MatchRange[m2][m1] for m1 in [0, 1]] for m2 in [0, 1]]
	PriorityInActive = Priority
	for i in range(len(A) + len(B)):
		if ABStacks[0][-1] == ABStacks[1][-1]:
			if MatchRangeActive[0][0] == MatchRangeActive[1][0]:
				AltInd = PriorityActive
			else:
				MatchRangeInActive = [[MatchRangeActive[m2][m1] for m1 in [0, 1]] for m2 in [0, 1]]
				PriorityInActive = PriorityActive
				(MatchRangeActive, PriorityActive) = GetMatch(ABStacks)
				AltInd = PriorityActive
		elif ABStacks[0][-1] < ABStacks[1][-1]:
			AltInd = 0
		else:
			AltInd = 1
		OutStr += ABStacks[AltInd].pop()
		if len(ABStacks[0]) == 0 or len(ABStacks[1]) == 0:
			break
		MatchRangeActive = UpdateMatchRange(MatchRangeActive, AltInd)
		MatchRangeInActive = UpdateMatchRange(MatchRangeInActive, AltInd)
		MRLenAct = MRLen(MatchRangeActive)
		MRLenInAct = MRLen(MatchRangeInActive)
		if MRLenInAct > 0:
			if MatchRangeInActive[0][0] == MatchRangeInActive[1][0] and MatchRangeActive[0][0] != MatchRangeActive[1][0]:
				(MatchRangeActive, MatchRangeInActive) = (MatchRangeInActive, MatchRangeActive)
				(MRLenAct, MRLenInAct) = (MRLenInAct, MRLenAct)
				(PriorityActive, PriorityInActive) = (PriorityInActive, PriorityActive)
		if MRLenAct < 1:
			if ABStacks[0][-1] == ABStacks[1][-1]:
				(MatchRangeActive, PriorityActive) = GetMatch(ABStacks)
				MRLenAct = MRLen(MatchRangeActive)
	for i in ABStacks:
		if len(i) > 0:
			for j in range(len(i)):
				OutStr += i.pop()
	print(OutStr)


def lexico(a, b, ans):
	if a == '':
		return ans + b
	if b == '':
		return ans + a
	if len(a) > len(b):
		(a, b) = (b, a)
	if a < b:
		return lexico(a[1:], b, ans + a[0])
	else:
		return lexico(a, b[1:], ans + b[0])

def lexico1(a, b):
	if len(a) > len(b):
		(a, b) = (b, a)
	op = ''
	(c_a, c_b) = (0, 0)
	while c_a != len(a) and c_b != len(b):
		if a[c_a:] < b[c_b:]:
			op += a[c_a]
			c_a += 1
		else:
			op += b[c_b]
			c_b += 1
	op += a[c_a:] + b[c_b:]
	return op
t = int(input().strip())
a = []
b = []
for i in range(t):
	a.append(input().strip())
	b.append(input().strip())
for i in range(t):
	ans = lexico1(a[i] + 'z', b[i] + 'z')
	print(ans[:-2])


times = int(input())
for n in range(times):
	first = input() + 'z'
	second = input() + 'z'
	output = ''
	while len(first) > 0 or len(second) > 0:
		if len(first) == 0:
			output += second
			second = ''
		elif len(second) == 0:
			output += first
			first = ''
		elif first < second:
			output += first[0]
			first = first[1:]
		else:
			output += second[0]
			second = second[1:]
	print(output.replace('z', ''))


def compare(s1, s2, i, j):
	i = len(s1) - 1
	j = len(s2) - 1
	while i >= 0 and j >= 0:
		if s1[i] > s2[j]:
			return False
		elif s1[i] < s2[j]:
			return True
		else:
			i -= 1
			j -= 1
	return i < 0
n = int(input())
for _ in range(n):
	s1 = list(input() + 'z')
	s2 = list(input() + 'z')
	mem_1 = set()
	mem_2 = set()
	i = 0
	j = 0
	result = []
	while True:
		if i >= len(s1):
			result += list(s2[j:])
			break
		if j >= len(s2):
			result += list(s1[i:])
			break
		if s1[i] > s2[j]:
			result.append(s2[j])
			j += 1
		elif s1[i] < s2[j]:
			result.append(s1[i])
			i += 1
		elif (i, j) in mem_1:
			result.append(s1[i])
			i += 1
		elif (i, j) in mem_2:
			result.append(s2[j])
			j += 1
		else:
			temp_set = set()
			ii = i
			jj = j
			while ii < len(s1) and jj < len(s2):
				temp_set.add((ii, jj))
				if s1[ii] < s2[jj]:
					result.append(s1[i])
					i += 1
					mem_1 |= temp_set
					break
				elif s1[ii] > s2[jj]:
					result.append(s2[j])
					j += 1
					mem_2 |= temp_set
					break
				else:
					ii += 1
					jj += 1
			if ii == len(s1):
				result.append(s1[i])
				i += 1
				mem_1 |= temp_set
	result.pop()
	result.pop()
	print(''.join(result))


T = int(input())
for i in range(T):
	first = input().strip()
	second = input().strip()
	output = ''
	while first != '' or second != '':
		if first == '':
			output += second[0]
			second = second[1:]
		elif second == '':
			output += first[0]
			first = first[1:]
		elif first + 'z' <= second + 'z':
			output += first[0]
			first = first[1:]
		else:
			output += second[0]
			second = second[1:]
	print(output)


def main(A, B):
	A_index = 0
	B_index = 0
	if len(A) == 0 or len(B) == 0:
		return A + B
	final = ''
	while A_index < len(A) and B_index < len(B):
		if A[A_index:] + 'z' < B[B_index:] + 'z':
			final += A[A_index]
			A_index += 1
		else:
			final += B[B_index]
			B_index += 1
	final += A[A_index:] + B[B_index:]
	return final
N = int(input())
for i in range(N):
	A = input()
	B = input()
	print(main(A, B))


def lex(a, b):
	i = 0
	j = 0
	a += 'z'
	b += 'z'
	lis = []
	while a[i] != 'z' and b[j] != 'z':
		if a[i:] <= b[j:]:
			lis.append(a[i])
			i += 1
		elif b[j:] < a[i:]:
			lis.append(b[j])
			j += 1
	while a[i] != 'z':
		lis.append(a[i])
		i += 1
	while b[j] != 'z':
		lis.append(b[j])
		j += 1
	print(''.join(lis))
for _ in range(int(input())):
	a = input()
	b = input()
	lex(a, b)


def merge(s1, s2):
	(l1, l2) = (len(s1), len(s2))
	(x1, x2) = (0, 0)
	while x1 < l1 and x2 < l2:
		if s1[x1:] <= s2[x2:]:
			yield s1[x1]
			x1 += 1
		else:
			yield s2[x2]
			x2 += 1
	if x1 < l1:
		yield s1[x1:]
	if x2 < l2:
		yield s2[x2:]
for _ in range(int(input())):
	(s1, s2) = (input(), input())
	print(''.join(merge(s1 + 'z', s2 + 'z'))[:-2])


T = int(input())
for T_i in range(T):
	s1 = input() + 'ZZZZZ'
	s2 = input() + 'ZZZZZ'
	i = j = 0
	ans = ''
	while i < len(s1) - 5 or j < len(s2) - 5:
		if i == len(s1) - 5:
			ans += s2[j]
			j += 1
		elif j == len(s2) - 5:
			ans += s1[i]
			i += 1
		elif s1[i] == s2[j]:
			if s1[i:] <= s2[j:]:
				ans += s1[i]
				i += 1
			else:
				ans += s2[j]
				j += 1
		elif s1[i] < s2[j]:
			ans += s1[i]
			i += 1
		else:
			ans += s2[j]
			j += 1
	print(ans)


for x in range(int(input())):
	a = input().strip() + '|'
	b = input().strip() + '|'
	(ai, bi) = (0, 0)
	r = ''
	while ai < len(a) - 1 and bi < len(b) - 1:
		if a[ai:] > b[bi:]:
			r += b[bi]
			bi += 1
		else:
			r += a[ai]
			ai += 1
	r = r + a[ai:-1] + b[bi:-1]
	print(r)


for _ in range(int(input())):
	a = input() + '['
	b = input() + '['
	output = ''
	for _ in range(len(a) + len(b) - 2):
		if a < b:
			output += a[0]
			a = a[1:]
		else:
			output += b[0]
			b = b[1:]
	print(output)


T = int(input())
for _ in range(T):
	A = input().strip()
	B = input().strip()
	result = ''
	while A and B:
		_next = A + 'z' > B + 'z'
		if _next:
			to_attach = B[0]
			B = B[1:]
		else:
			to_attach = A[0]
			A = A[1:]
		result += to_attach
	result += A
	result += B
	print(result)


T = int(input())

def make_lex_smallest(A, B):
	res = []
	i = 0
	j = 0
	lenA = len(A)
	lenB = len(B)
	A += 'z'
	B += 'z'
	while i < lenA and j < lenB:
		if ord(A[i]) == ord(B[j]):
			if A[i:] < B[j:]:
				res.append(A[i])
				i += 1
			else:
				res.append(B[j])
				j += 1
		elif ord(A[i]) < ord(B[j]):
			res.append(A[i])
			i += 1
		else:
			res.append(B[j])
			j += 1
	if i == lenA:
		res += B[j:-1]
	else:
		res += A[i:-1]
	return ''.join(res)
for i in range(T):
	A = input()
	B = input()
	res = make_lex_smallest(A, B)
	print(res)


import sys
import re
t = int(input().strip())
for i in range(0, t):
	s1 = input().strip()
	s2 = input().strip()
	len1 = len(s1)
	len2 = len(s2)
	i = 0
	j = 0
	l = []
	while i < len1 and j < len2:
		if s1[i] < s2[j]:
			l.append(s1[i])
			i += 1
		elif s1[i] > s2[j]:
			l.append(s2[j])
			j += 1
		elif s1[i:] + 'z' < s2[j:] + 'z':
			l.append(s1[i])
			i += 1
		else:
			l.append(s2[j])
			j += 1
	if i != len1:
		print(''.join(l) + s1[i:])
	else:
		print(''.join(l) + s2[j:])


t = int(input().strip())
for _ in range(t):
	a = input().strip()
	b = input().strip()
	s = []
	while a and b:
		i = 0
		while i < len(a) and i < len(b):
			ca = a[i]
			cb = b[i]
			if ca != cb:
				break
			i += 1
		else:
			if len(a) > len(b):
				s.append(a[0])
				a = a[1:]
			else:
				s.append(b[0])
				b = b[1:]
			continue
		if ca > cb:
			s.extend(b[:i + 1])
			b = b[i + 1:]
		else:
			s.extend(a[:i + 1])
			a = a[i + 1:]
	s += a + b
	print(''.join(s))


t = int(input())
for _ in range(t):
	s1 = input()
	s2 = input()
	(lens1, lens2) = (len(s1), len(s2))
	(i1, i2) = (0, 0)
	flast = 0
	while i1 < lens1 and i2 < lens2:
		if s1[i1] == s2[i2]:
			print(s1[i1], end='')
			(k1, k2) = (i1, i2)
			if flast == 0:
				while k1 < lens1 and k2 < lens2 and (s1[k1] == s2[k2]):
					k1 += 1
					k2 += 1
				if k2 == lens2 or (k1 < lens1 and k2 < lens2 and (s1[k1] < s2[k2])):
					flast = 1
				else:
					flast = 2
			i1 += flast == 1
			i2 += flast == 2
		elif s1[i1] < s2[i2]:
			print(s1[i1], end='')
			flast = 0
			i1 += 1
		else:
			print(s2[i2], end='')
			flast = 0
			i2 += 1
	print(s1[i1:] + s2[i2:])


t = int(input())
for _2 in range(t):
	a = input() + 'z'
	b = input() + 'z'
	(a_c, b_c) = (0, 0)
	final = []
	for _ in range(len(a) + len(b)):
		if a[a_c:] < b[b_c:]:
			final.append(a[a_c])
			a_c += 1
		else:
			final.append(b[b_c])
			b_c += 1
		if a_c == len(a) - 1:
			final.extend(b[b_c:-1])
			break
		elif b_c == len(b) - 1:
			final.extend(a[a_c:-1])
			break
	print(''.join(final))


T = int(input())

def alpha_min(a, b):
	la = len(a)
	lb = len(b)
	a += 'z'
	b += 'z'
	i = j = 0
	res = ''
	while i != la and j != lb:
		if a[i:] < b[j:]:
			res += a[i]
			i += 1
		else:
			res += b[j]
			j += 1
	res += a[i:-1] + b[j:-1]
	return res
for _ in range(T):
	a = input().strip()
	b = input().strip()
	print(alpha_min(a, b))


T = int(input().strip())

def fun(A, B):
	A += 'a'
	B += 'a'
	i = 0
	x = True
	if A == B:
		if len(A) == 2:
			return ([A[0]], [], B[:-1])
		a = 0
		i = 2
	else:
		while x == True:
			if A[i] < B[i]:
				x = False
				a = 0
			elif A[i] > B[i]:
				x = False
				a = 1
			else:
				i += 1
	if i > 0:
		H = []
		c1 = 0
		c2 = 0
		while c1 < i and c2 < i:
			if A[0] < B[0] or (A[0] == B[0] and a == 0):
				H.append(A[0])
				A = A[1:]
				c1 += 1
			else:
				H.append(B[0])
				B = B[1:]
				c2 += 1
	elif a == 0:
		H = [A[0]]
		A = A[1:]
	else:
		H = [B[0]]
		B = B[1:]
	return (H, A[:-1], B[:-1])
for i in range(T):
	A = input().strip()
	B = input().strip()
	C = []
	while len(A) > 0 and len(B) > 0:
		(H, A, B) = fun(A, B)
		C += H
	C = ''.join(C)
	if len(A) == 0:
		C += B
	else:
		C += A
	print(C)


import sys
cases = int(input().strip())
for _ in range(cases):
	stra = input().strip()
	strb = input().strip()
	lena = len(stra)
	lenb = len(strb)
	(i, j) = (0, 0)
	res = ''
	while i < lena and j < lenb:
		if stra[i] < strb[j]:
			res += stra[i]
			i += 1
		elif stra[i] > strb[j]:
			res += strb[j]
			j += 1
		elif i != j:
			delta = 1
			try:
				while stra[i + delta] == strb[j + delta]:
					delta += 1
				if stra[i + delta] < strb[j + delta]:
					res += stra[i:i + delta]
					i += delta
				elif stra[i + delta] > strb[j + delta]:
					res += strb[j:j + delta]
					j += delta
			except:
				if j == 0:
					stra = stra[1:]
					lena = len(stra)
					(i, j) = (0, 0)
				else:
					res += stra[i:i + delta]
					i += delta
		else:
			delta = 1
			try:
				while stra[i + delta] == strb[j + delta]:
					delta += 1
				if stra[i + delta] < strb[j + delta]:
					res += stra[i]
					i += 1
				elif stra[i + delta] > strb[j + delta]:
					res += strb[j]
					j += 1
			except:
				res += strb[j]
				j += 1
	if i >= lena:
		res += strb[j:]
	elif j >= lenb:
		res += stra[i:]
	print(res)


def minimum(s1, s2):
	(i, j) = (0, 0)
	n = len(s1)
	m = len(s2)
	s1 += 'z'
	s2 += 'z'
	output = ''
	while i < n and j < m:
		if s1[i] < s2[j]:
			output += s1[i]
			i += 1
		elif s1[i] > s2[j]:
			output += s2[j]
			j += 1
		elif s1[i:] < s2[j:]:
			output += s1[i]
			i += 1
		elif s1[i:] > s2[j:]:
			output += s2[j]
			j += 1
		else:
			output += s1[i]
			i += 1
	if i < n:
		output += s1[i:n]
	if j < m:
		output += s2[j:m]
	return output
n = int(input())
for test in range(n):
	s1 = input()
	s2 = input()
	print(minimum(s1, s2))


N = int(input())
for i in range(0, N):
	D1 = input()
	A1 = input()
	D1 += 'z'
	A1 += 'z'
	D = [x for x in D1]
	A = [x for x in A1]
	iD = 0
	iA = 0
	Results = ''
	while len(Results) < len(D) + len(A):
		if iD >= len(D):
			Results += ''.join(A[iA:])
			break
		if iA >= len(A):
			Results += ''.join(D[iD:])
			break
		if A[iA] == D[iD]:
			if D1[iD:] > A1[iA:]:
				Results += A[iA]
				iA += 1
				continue
			else:
				Results += D[iD]
				iD += 1
				continue
		if A[iA] < D[iD]:
			Results += A[iA]
			iA += 1
			continue
		if A[iA] > D[iD]:
			Results += D[iD]
			iD += 1
			continue
	print(Results[:-2])


n = int(input().strip())
names = []
for i in range(n * 2):
	names.append(input().strip() + 'z')

def func(mas):
	mas_len = 0
	for i in mas:
		mas_len += len(i)
	res = ''
	for elem in range(0, mas_len):
		maxStr = ''
		if len(mas[0]) > 0 and len(mas[1]):
			if mas[0][0] < mas[1][0]:
				maxStr = mas[0][0]
				mas[0] = mas[0][1:]
			elif mas[0][0] > mas[1][0]:
				maxStr = mas[1][0]
				mas[1] = mas[1][1:]
			elif mas[0][1:] < mas[1][1:]:
				maxStr = mas[0][0]
				mas[0] = mas[0][1:]
			elif mas[0][1:] > mas[1][1:]:
				maxStr = mas[1][0]
				mas[1] = mas[1][1:]
			else:
				maxStr = mas[0][0]
				mas[0] = mas[0][1:]
		elif len(mas[0]) > 0:
			maxStr = mas[0][0]
			mas[0] = mas[0][1:]
		elif len(mas[1]) > 0:
			maxStr = mas[1][0]
			mas[1] = mas[1][1:]
		res += maxStr
	print(res[:mas_len - 2])
while len(names) > 0:
	func(names[:2])
	names = names[2:]