Read problem statements in [Hindi], [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

You are given two strings $S$ and $R$. You may reorder the characters in the string $R$ in any way; let's denote the resulting string by $R_{r}$. This reordered string is *valid* if it contains all substrings of $S$, i.e. for each substring $s$ of $S$ (including $S$ itself), $R_{r}$ contains $s$ as a substring.

Find the lexicographically smallest valid reordered string or determine that there is no such valid string.

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains a single string $S$.
The second line contains a single string $R$.

------  Output ------
For each test case, print a single line containing one string — the lexicographically smallest valid reordered string, or "Impossible" if there is no such string.

------  Constraints ------
$1 ≤ T ≤ 1,000$
$1 ≤ |S|, |R| ≤ 10^{5}$
$S$ and $R$ contain only lowercase English letters
the sum of $|S|$ over all test cases does not exceed $10^{6}$
the sum of $|R|$ over all test cases does not exceed $10^{6}$

------  Subtasks ------
Subtask #1 (50 points):
$1 ≤ |S|, |R| ≤ 1,000$
$S$ and $R$ contain only the characters 'a' and 'b'
the sum of $|S|$ in all test cases does not exceed $10^{4}$
the sum of $|R|$ in all test cases does not exceed $10^{4}$

Subtask #2 (50 points): original constraints

----- Sample Input 1 ------ 
4
aa
ababab
aaa
ramialsadaka
said
sryhieni
code
codeisfun
----- Sample Output 1 ------ 
aaabbb
aaaaadiklmrs
Impossible
codefinsu

Source: codechef | Difficulty: HARD
Tags: Greedy algorithms

Constructive algorithms


Solutions:
from collections import Counter
for _ in range(int(input())):
	s = input()
	r = list(input())
	r.sort()
	d = Counter(s)
	e = Counter(r)
	m = 0
	i = 0
	for i in d.keys():
		if d[i] > e[i]:
			print('Impossible')
			m = 1
			break
		else:
			e[i] -= d[i]
	if m:
		continue
	if s < s[0] * len(s):
		check = 1
	else:
		check = 0
	k = 1
	for j in e.keys():
		if check:
			if j == s[0] and k:
				k = 0
				for n in s:
					print(n, end='')
			for z in range(e[j]):
				print(j, end='')
		elif check == 0:
			for z in range(e[j]):
				print(j, end='')
			if j >= s[0] and k:
				k = 0
				for n in s:
					print(n, end='')
	print()


def solve():
	freq = [0] * 26
	freqr = [0] * 26
	for char in s:
		freq[ord(char) - ord('a')] += 1
	for char in r:
		freqr[ord(char) - ord('a')] += 1
	for i in range(26):
		if freq[i] > freqr[i]:
			print('Impossible')
			return
	ans = ''
	i = 0
	while chr(i + ord('a')) < s[0]:
		ans = ans + chr(i + ord('a')) * (freqr[i] - freq[i])
		i += 1
	if s[0] * len(s) > s:
		ans = ans + s
	else:
		ans = ans + chr(i + ord('a')) * (freqr[i] - freq[i])
		i += 1
		ans = ans + s
	while i < 26:
		ans = ans + chr(i + ord('a')) * (freqr[i] - freq[i])
		i += 1
	print(ans)
	return
t = int(input())
while t > 0:
	t -= 1
	s = input()
	r = input()
	if len(r) < len(s):
		print('Impossible')
	else:
		solve()


from collections import Counter
for _ in range(int(input())):
	s = input()
	r = input()
	d = Counter(s)
	e = Counter(r)
	m = 0
	i = 0
	for i in d.keys():
		if d[i] > e[i]:
			print('Impossible')
			m = 1
			break
		else:
			e[i] -= d[i]
	if m:
		continue
	if s < s[0] * len(s):
		check = 1
	else:
		check = 0
	left = []
	right = []
	for j in e.keys():
		if check:
			if j < s[0]:
				for z in range(e[j]):
					left.append(j)
			else:
				for z in range(e[j]):
					right.append(j)
		elif j <= s[0]:
			for z in range(e[j]):
				left.append(j)
		else:
			for z in range(e[j]):
				right.append(j)
	left.sort()
	right.sort()
	print(''.join(left) + ''.join(s) + ''.join(right))


from collections import Counter

def fun(x, y):
	x_c = Counter(x)
	y_c = Counter(y)
	m = 1
	for z in x_c.keys():
		if x_c[z] > y_c[z]:
			m = 0
			break
		else:
			y_c[z] -= x_c[z]
	if m:
		left = []
		right = []
		if x < x[0] * len(x):
			for (i, j) in y_c.items():
				if i < x[0]:
					left.append(i * j)
				else:
					right.append(i * j)
		else:
			for (i, j) in y_c.items():
				if i <= x[0]:
					left.append(i * j)
				else:
					right.append(i * j)
		left.sort()
		right.sort()
		return ''.join(left) + x + ''.join(right)
	else:
		return 'Impossible'
for _ in range(int(input())):
	a = input().strip()
	b = input().strip()
	print(fun(a, b))


from collections import Counter

def fun(x, y):
	x_c = Counter(x)
	y_c = Counter(y)
	flag = True
	for (alp, cnt) in x_c.items():
		cnt2 = y_c.get(alp)
		if cnt2:
			if cnt2 < cnt:
				flag = False
				break
			else:
				y_c[alp] -= x_c[alp]
		else:
			flag = False
			break
	if flag:
		left = []
		right = []
		if x < x[0] * len(x):
			for (i, j) in y_c.items():
				if i < x[0]:
					left.append(i * j)
				else:
					right.append(i * j)
		else:
			for (i, j) in y_c.items():
				if i <= x[0]:
					left.append(i * j)
				else:
					right.append(i * j)
		left.sort()
		right.sort()
		return ''.join(left) + x + ''.join(right)
	else:
		return 'Impossible'
for _ in range(int(input())):
	a = input()
	b = input()
	print(fun(a, b))


try:
	for _ in range(int(input())):
		s = input()
		r = input()
		ls = len(s)
		lr = len(r)
		list1 = [0] * 26
		list2 = [0] * 26
		for i in range(ls):
			x = s[i]
			list1[ord(x) - 97] += 1
		for i in range(lr):
			x = r[i]
			list2[ord(x) - 97] += 1
		f = 0
		for i in range(26):
			if list1[i] > list2[i]:
				f = 1
				break
		if f == 1:
			print('Impossible')
		else:
			for i in range(ls):
				x = s[i]
				list2[ord(x) - 97] -= 1
			ele = s[0]
			ele = ord(ele) - 97
			for i in range(26):
				if list2[i] > 0 and i < ele:
					ss = chr(i + 97) * list2[i]
					print(ss, end='')
					list2[i] = 0
			if list2[ele] > 0:
				ss = chr(ele + 97) * list2[ele]
				if ls > 1:
					ff = 0
					for i in range(1, ls):
						if s[i] != s[0]:
							if s[i] < s[0]:
								ff = 1
							break
					if ff == 1:
						print(s, end='')
						print(ss, end='')
						list2[ele] = 0
					else:
						print(ss, end='')
						list2[ele] = 0
						print(s, end='')
				else:
					print(ss, end='')
					list2[ele] = 0
					print(s, end='')
			else:
				print(s, end='')
			for i in range(26):
				if list2[i] > 0:
					ss = chr(i + 97) * list2[i]
					print(ss, end='')
			print()
except:
	pass


for _ in range(int(input())):
	a = input().strip()
	b = list(input().strip())
	m = len(a)
	from collections import Counter
	n = len(b)
	c1 = Counter(a)
	f = 1
	c2 = Counter(b)
	for i in range(97, 123):
		ch = chr(i)
		if c2[ch] < c1[ch]:
			f = 0
	if f == 0:
		print('Impossible')
		continue
	for i in range(97, 123):
		ch = chr(i)
		c2[ch] -= c1[ch]
	rem = []
	mini = 'z' * 10000000
	for i in range(97, 123):
		ch = chr(i)
		rem += list(ch * c2[ch])
	rem.sort()
	less = [i for i in rem if i < a[0]]
	more = [i for i in rem if i > a[0]]
	eql = [i for i in rem if i == a[0]]
	if len(a) == 1 or len(set(a)) == 1:
		ans = less + eql + list(a) + more
		print(''.join(ans))
	else:
		ch = a[0]
		i = 1
		while i < m and a[i] == ch:
			i += 1
		if a[i] > a[0]:
			ans = less + eql + list(a) + more
			print(''.join(ans))
		else:
			ans = less + list(a) + eql + more
			print(''.join(ans))


for _ in range(int(input())):
	a = input().strip()
	b = list(input().strip())
	m = len(a)
	from collections import Counter
	n = len(b)
	c1 = Counter(a)
	f = 1
	c2 = Counter(b)
	for i in range(97, 123):
		ch = chr(i)
		if c2[ch] < c1[ch]:
			f = 0
	if f == 0:
		print('Impossible')
		continue
	for i in range(97, 123):
		ch = chr(i)
		c2[ch] -= c1[ch]
	rem = []
	mini = 'z' * 10000000
	for i in range(97, 123):
		ch = chr(i)
		rem += list(ch * c2[ch])
	rem.sort()
	prev = rem[:]
	for i in range(len(rem)):
		rem.insert(i, a)
		if ''.join(rem) < mini:
			mini = ''.join(rem)
		rem = prev[:]
	rem.append(a)
	if ''.join(rem) < mini:
		mini = ''.join(rem)
	print(mini)


t = int(input())
for _ in range(t):
	z = ord('a')
	s = input()
	r = input()
	first = ord(s[0]) - ord('a')
	l = [0 for i in range(26)]
	for i in range(len(r)):
		x = ord(r[i]) - ord('a')
		l[x] = l[x] + 1
	for i in range(len(s)):
		x = ord(s[i]) - ord('a')
		l[x] = l[x] - 1
	valid = True
	for i in range(26):
		valid = valid and l[i] >= 0
	if not valid:
		print('Impossible')
		continue
	ans = ''
	one = 0
	two = -1
	for i in range(first):
		for j in range(l[i]):
			ans = ans + chr(z + i)
	for i in range(0, len(s)):
		if ord(s[i]) - ord('a') > first:
			break
		elif ord(s[i]) - ord('a') < first:
			ans = ans + s
			s = ''
			break
	while l[first]:
		ans = ans + chr(z + first)
		l[first] = l[first] - 1
	ans = ans + s
	for i in range(first + 1, 26):
		for j in range(l[i]):
			ans = ans + chr(z + i)
	print(ans)


t = int(input())
for i in range(0, t):
	s = input()
	r = input()
	l1 = []
	l2 = []
	l3 = []
	f = 0
	for j in range(0, 26):
		l1.append(0)
		l2.append(0)
		l3.append(0)
	for j in s:
		l1[ord(j) - 97] += 1
	for j in r:
		l2[ord(j) - 97] += 1
	for j in range(0, 26):
		l3[j] = l2[j] - l1[j]
		if l3[j] < 0:
			print('Impossible')
			f = 1
			break
	if f == 0:
		m = s
		ft = ''
		bc = ''
		f1 = ''
		b1 = ''
		for j in range(0, 26):
			for k in range(0, l3[j]):
				m1 = f1 + chr(97 + j) + s + b1
				m2 = f1 + s + b1 + chr(97 + j)
				if m1 < m2:
					m = m1
					f1 += chr(97 + j)
				else:
					m = m2
					b1 += chr(97 + j)
		ans = f1 + s + b1
		print(ans)


t = int(input())
for i in range(t):
	s = input()
	r = input()
	count_s = {}
	count_r = {}
	for c in s:
		if c not in count_s:
			count_s[c] = 1
		else:
			count_s[c] += 1
	for c in r:
		if c not in count_r:
			count_r[c] = 1
		else:
			count_r[c] += 1
	ok = True
	for c in count_s:
		if c not in count_r or count_s[c] > count_r[c]:
			print('Impossible')
			ok = False
			break
	if ok:
		for c in count_r:
			if c in count_s:
				count_r[c] -= count_s[c]
		key = [k for k in count_r.keys() if count_r[k] > 0]
		key.sort()
		first = s[0]
		res = []
		index = 0
		while index < len(key) and key[index] < first:
			res.append(key[index] * count_r[key[index]])
			index += 1
		if index < len(key) and key[index] == first:
			s_index = 0
			while s_index < len(s) and key[index] == s[s_index]:
				s_index += 1
			if s_index < len(s) and key[index] < s[s_index]:
				res.append(key[index] * count_r[key[index]])
				index += 1
		res.append(s)
		for j in range(index, len(key)):
			res.append(key[j] * count_r[key[j]])
		print(''.join(res))


from collections import Counter
for _ in range(int(input())):
	s = input()
	r = input()
	sc = Counter(s)
	rc = Counter(r)
	flag = 0
	for i in sc:
		if sc[i] > rc[i]:
			flag = 1
			break
	if flag == 1:
		print('Impossible')
		continue
	for i in s:
		rc[i] -= 1
	t1 = []
	t2 = []
	t3 = ''
	for i in rc:
		if rc[i]:
			if i > s[0]:
				t1.append(i * rc[i])
			elif i < s[0]:
				t2.append(i * rc[i])
			else:
				t3 += i * rc[i]
	print(min(''.join(sorted(t2) + [t3] + [s] + sorted(t1)), ''.join(sorted(t2) + [s] + [t3] + sorted(t1))))


from collections import Counter
t = int(input())
for _ in range(0, t):
	s1 = input()
	s2 = input()
	c1 = Counter(s1)
	c2 = Counter(s2)
	f = 1
	for i in s1:
		c2[i] = c2[i] - 1
		if c2[i] < 0:
			f = 0
			break
	if f:
		a = s1[0]
		e = list(c2.elements())
		e.sort()
		m1 = ''
		m2 = ''
		m3 = ''
		c = 0
		for i in e:
			if i < a:
				m1 = m1 + i
			elif i > a:
				m2 = m2 + i
			else:
				m3 = m3 + i
		a1 = m1 + m3 + s1 + m2
		a2 = m1 + s1 + m3 + m2
		if a1 < a2:
			print(a1)
		else:
			print(a2)
	else:
		print('Impossible')


from collections import Counter
t = int(input())
while t:
	s = input()
	r = input()
	c1 = Counter(s)
	c2 = Counter(r)
	flag = True
	for (key, val) in c1.items():
		if c2[key] >= val:
			c2[key] -= val
		else:
			flag = False
			break
	if flag:
		ans = ''
		for (key, val) in c2.items():
			if val > 0:
				ans = ans + key
		temp = sorted(ans)
		temp_len = len(temp)
		ns = ''
		i = 0
		if temp != []:
			while i < temp_len and s[0] > temp[i]:
				ns = ns + temp[i] * c2[temp[i]]
				c2[temp[i]] = 0
				i += 1
			if c2[s[0]] > 0:
				if s <= s[0] * len(s):
					ns = ns + s
					ns = ns + c2[s[0]] * s[0]
					c2[s[0]] = 0
				else:
					ns = ns + c2[s[0]] * s[0]
					ns = ns + s
					c2[s[0]] = 0
				for j in range(i + 1, temp_len):
					ns = ns + temp[j] * c2[temp[j]]
					c2[temp[j]] = 0
			else:
				ns = ns + s
				for j in range(i, temp_len):
					ns = ns + temp[j] * c2[temp[j]]
					c2[temp[j]] = 0
			print(ns)
		else:
			print(s)
	else:
		print('Impossible')
	t -= 1


t = int(input())
for _ in range(t):
	s = input()
	r = input()
	cnt = [0 for i in range(300)]
	for i in r:
		cnt[ord(i)] += 1
	imp = 0
	for i in s:
		cnt[ord(i)] -= 1
		if cnt[ord(i)] < 0:
			imp = 1
			break
	if imp == 1:
		print('Impossible')
		continue
	ans = []
	for j in range(ord('a'), ord(s[0])):
		while cnt[j] > 0:
			ans.append(chr(j))
			cnt[j] -= 1
	flet = ord(s[0])
	for j in range(0, len(s)):
		if s[j] > s[0]:
			break
		if s[j] < s[0]:
			ans += list(s)
			s = ''
			break
	while cnt[flet] > 0:
		ans.append(chr(flet))
		cnt[flet] -= 1
	ans += list(s)
	for j in range(ord('a'), ord('z') + 1):
		while cnt[j] > 0:
			ans.append(chr(j))
			cnt[j] -= 1
	print(*ans, sep='')


alpha = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
for _ in range(int(input())):
	count = {}
	for i in alpha:
		count[i] = 0
	pat = input()
	patlist = list(pat)
	search = list(input())
	for i in search:
		count[i] += 1
	flag = True
	for i in patlist:
		count[i] -= 1
	ans = []
	small = True
	for i in range(len(patlist) - 1):
		if patlist[i] > patlist[i + 1]:
			break
		elif patlist[i] < patlist[i + 1]:
			small = False
			break
	for i in alpha:
		if i == patlist[0] and small:
			ans.append(pat)
		if count[i] < 0:
			flag = False
			break
		ans.extend([i for z in range(count[i])])
		if i == patlist[0] and small == False:
			ans.append(pat)
	if flag:
		print(''.join(ans))
	else:
		print('Impossible')


for _ in range(int(input())):
	n = input()
	m = list(input())
	s = ''
	t = 1
	vi = n[0]
	zq = 1
	se = vi
	d = {}
	for i in m:
		if i not in d:
			d[i] = 0
		d[i] += 1
	for i in n:
		if i in d and d[i] != 0:
			s += i
			d[i] -= 1
		else:
			print('Impossible')
			t = 0
			break
		if zq and i != se:
			zq = 0
			se = i
	if t:
		f = ''
		for i in range(26):
			if chr(ord('a') + i) in d:
				if ord('a') + i > ord(s[0]):
					s += chr(ord('a') + i) * d[chr(ord('a') + i)]
				elif ord('a') + i == ord(s[0]):
					if chr(ord('a') + i) > se:
						s += chr(ord('a') + i) * d[chr(ord('a') + i)]
					else:
						f += chr(ord('a') + i) * d[chr(ord('a') + i)]
				else:
					f += chr(ord('a') + i) * d[chr(ord('a') + i)]
		print(f + s)


for _ in range(int(input())):
	s = input().strip()
	r = input().strip()
	possible = True
	sdic = {chr(i): 0 for i in range(97, 123)}
	rdic = {chr(i): 0 for i in range(97, 123)}
	for i in s:
		sdic[i] += 1
	for i in r:
		rdic[i] += 1
	for key in s:
		if sdic[key] > rdic[key]:
			possible = False
			break
	if not possible:
		print('Impossible')
	else:
		output = ''
		output1 = ''
		output2 = ''
		for i in s:
			rdic[i] -= 1
		firstChar = s[0]
		l = list(rdic.keys())
		i = 97
		while i < ord(firstChar):
			output1 += rdic[chr(i)] * chr(i)
			output2 += rdic[chr(i)] * chr(i)
			rdic[chr(i)] = 0
			i += 1
		toFind = i
		First = True
		output1 += rdic[chr(i)] * chr(i)
		output1 += s
		output2 += s
		output2 += rdic[chr(i)] * chr(i)
		rdic[chr(i)] = 0
		output = min(output1, output2)
		for key in rdic:
			tmp = rdic[key] * key
			output += tmp
		print(output)


import collections
t = int(input())
for _ in range(t):
	s = input()
	r = collections.Counter(input())
	r.subtract(s)
	if any((v < 0 for v in r.values())):
		print('Impossible')
	else:
		r = [*r.elements(), s]
		r.sort(key=lambda x: x[0] + (x.lstrip(x[0]) or x)[0])
		print(''.join(r))


import string
import collections
t = int(input())
for _ in range(t):
	s = input()
	r = collections.Counter(input())
	r.subtract(s)
	if any((v < 0 for v in r.values())):
		print('Impossible')
	else:
		c = chr(ord(s[0]) - ((s.lstrip(s[0]) or s)[0] < s[0]))
		print(''.join((x * r[x] + s * (x == c) for x in string.ascii_lowercase)))


from string import ascii_lowercase

def getSolo(s):
	x = list(s)
	new = []
	for i in x:
		if i in new:
			pass
		else:
			new.append(i)
	if len(new) == 1:
		return False
	else:
		return new[1]
for _ in range(int(input())):
	s = input()
	r = input()
	ans = ''
	(fs, fr) = ({}, {})
	for i in ascii_lowercase:
		fs[i] = 0
		fr[i] = 0
	for i in s:
		fs[i] += 1
	for i in r:
		fr[i] += 1
	canbedone = True
	for i in ascii_lowercase:
		if fs[i] > fr[i]:
			canbedone = False
			break
		else:
			fr[i] -= fs[i]
	if canbedone:
		for i in ascii_lowercase:
			if i == s[0]:
				next = getSolo(s)
				if next != False and next < s[0]:
					ans += s
					ans += str(i) * fr[i]
				else:
					ans += str(i) * fr[i]
					ans += s
			else:
				ans += str(i) * fr[i]
		print(ans)
	else:
		print('Impossible')


d = {}
t = int(input())
for i in range(t):
	rec = 1
	for x in range(ord('a'), ord('z') + 1):
		d[chr(x)] = 0
	s1 = input()
	s2 = input()
	for j in s2:
		d[j] += 1
	for j in s1:
		if d[j] == 0:
			rec = 0
			break
		else:
			d[j] -= 1
	if rec == 0:
		print('Impossible')
		continue
	li = []
	for m in d:
		cnt = d[m]
		for j in range(cnt):
			li.append(m)
	rec = 1
	tv = 0
	while tv < len(s1) - 1:
		if ord(s1[tv]) < ord(s1[tv + 1]):
			rec = 0
			break
		elif ord(s1[tv]) > ord(s1[tv + 1]):
			break
		tv += 1
	li.sort()
	if rec == 0:
		li.append(s1)
		li.sort()
		s3 = ''
		for x in li:
			s3 += x
		print(s3)
	elif d[s1[0]] > 0:
		for i in range(len(li)):
			if li[i] == s1[0]:
				li.insert(i, s1)
				break
		s3 = ''
		for x in li:
			s3 += x
		print(s3)
	else:
		li.append(s1)
		li.sort()
		s3 = ''
		for x in li:
			s3 += x
		print(s3)


import sys

def get_answer(s, r):
	first = ord(s[0])
	for i in s:
		if i in r:
			r = r.replace(i, '', 1)
		else:
			return 'Impossible'
	start = ''
	end = ''
	equal = ''
	r = sorted(r)
	for i in r:
		if ord(i) < first:
			start = start + i
		elif ord(i) == first:
			equal = equal + i
		else:
			end = end + i
	return min(start + equal + s + end, start + s + equal + end)
testcase = int(sys.stdin.readline())
while testcase > 0:
	s = sys.stdin.readline().strip('\n')
	r = sys.stdin.readline().strip('\n')
	print(get_answer(s, r))
	testcase = testcase - 1


for _ in range(int(input())):
	s = input()
	r = input()
	smap = [0] * 26
	rmap = [0] * 26
	flag = -1
	for i in range(len(s)):
		smap[ord(s[i]) - 97] += 1
	for i in range(len(r)):
		rmap[ord(r[i]) - 97] += 1
	for i in range(26):
		if rmap[i] < smap[i]:
			flag = 0
			break
	if flag == 0:
		print('Impossible')
	else:
		rmapx = rmap[:]
		string = ''
		for i in range(len(s)):
			string = string + s[i]
			rmap[ord(s[i]) - 97] -= 1
		ch = string[0]
		ch = ord(ch) - 97
		string2 = ''
		for i in range(ch):
			while rmap[i] != 0:
				string2 = string2 + chr(i + 97)
				rmap[i] -= 1
		string = string2 + string
		for i in range(ch, 26):
			while rmap[i] != 0:
				string = string + chr(i + 97)
				rmap[i] -= 1
		stringx = ''
		for i in range(len(s)):
			stringx = stringx + s[i]
			rmapx[ord(s[i]) - 97] -= 1
		ch = stringx[0]
		ch = ord(ch) - 97
		string2x = ''
		for i in range(ch + 1):
			while rmapx[i] != 0:
				string2x = string2x + chr(i + 97)
				rmapx[i] -= 1
		stringx = string2x + stringx
		for i in range(ch + 1, 26):
			while rmapx[i] != 0:
				stringx = stringx + chr(i + 97)
				rmapx[i] -= 1
		if stringx < string:
			print(stringx)
		else:
			print(string)


for _ in range(int(input())):
	s = input()
	r = input()
	smap = [0] * 26
	rmap = [0] * 26
	flag = -1
	for i in range(len(s)):
		smap[ord(s[i]) - 97] += 1
	for i in range(len(r)):
		rmap[ord(r[i]) - 97] += 1
	for i in range(26):
		if rmap[i] < smap[i]:
			flag = 0
			break
	if flag == 0:
		print('Impossible')
	else:
		string = ''
		for i in range(len(s)):
			string = string + s[i]
			rmap[ord(s[i]) - 97] -= 1
		ch = string[0]
		ch = ord(ch) - 97
		plsql = []
		string2 = ''
		for i in range(26):
			while rmap[i] != 0:
				plsql.append(chr(i + 97))
				rmap[i] -= 1
		plsql.append(string)
		comp = ''.join(plsql)
		for i in range(len(plsql) - 1, -1, -1):
			comp2 = ''.join(plsql)
			if comp > comp2:
				comp = comp2[:]
			if i == 0:
				break
			temp = plsql[i]
			plsql[i] = plsql[i - 1]
			plsql[i - 1] = temp
		print(comp)


t = int(input())
for _ in range(t):
	r = input()
	s = input()
	temp = list(set(s + r))
	d = dict()
	t = 0
	for i in temp:
		d[i] = s.count(i) - r.count(i)
		if d[i] < 0:
			print('Impossible')
			t = 1
			break
	if t == 1:
		continue
	temp.sort()
	res = ''
	jam = 0
	for i in temp:
		if i >= r[0] and jam == 0:
			if i * len(r) <= r:
				res = res + i * d[i] + r
				jam = 1
			else:
				res = res + r + i * d[i]
				jam = 1
		else:
			res = res + i * d[i]
	print(res)


for _ in range(int(input())):
	s = input()
	r = input()
	rp = r
	flag = True
	for i in range(len(s)):
		if s[i] not in rp:
			flag = False
			print('Impossible')
			break
		else:
			rp = rp.replace(s[i], '', 1)
	if flag == True:
		xy = []
		for i in range(len(rp)):
			xy.append(rp[i])
		xy.sort()
		rp = ''
		for i in xy:
			rp += i
		bfore = ''
		aftr = ''
		same = ''
		for i in rp:
			if i < s[0]:
				bfore += i
			elif i > s[0]:
				aftr += i
			else:
				same += i
		alpha = bfore + same + s + aftr
		beta = bfore + s + same + aftr
		if alpha < beta:
			print(alpha)
		else:
			print(beta)


from collections import defaultdict
t = int(input())
for i in range(t):
	s = input()
	r = input()
	if len(s) > len(r):
		print('Impossible')
	else:
		flag = 1
		count_s = defaultdict(lambda : 0)
		count_r = defaultdict(lambda : 0)
		for i in s:
			count_s[i] += 1
		for i in r:
			count_r[i] += 1
		for i in count_s:
			if count_r[i] >= count_s[i]:
				count_r[i] = count_r[i] - count_s[i]
			else:
				flag = 0
		rem_str = [i * count_r[i] for i in count_r]
		rem_str = ''.join(rem_str)
		rem_str = ''.join(sorted(rem_str))
		if flag == 1:
			left = ''
			right = ''
			eq = ''
			for i in rem_str:
				if i < s[0]:
					left += i
				elif i > s[0]:
					right += i
				else:
					eq += i
			ans = min(left + eq + s + right, left + s + eq + right)
			print(ans)
		else:
			print('Impossible')


t = int(input())
for _ in range(t):
	s = input()
	r = input()
	ds = {}
	dr = {}
	y = 0
	for i in s:
		if i not in ds.keys():
			ds[i] = 1
		else:
			ds[i] += 1
	for i in r:
		if i not in dr.keys():
			dr[i] = 1
		else:
			dr[i] += 1
	for i in ds.keys():
		if i not in dr.keys() or ds[i] > dr[i]:
			y = 1
			break
		else:
			dr[i] -= ds[i]
	if y == 1:
		print('Impossible')
	else:
		t = ''
		l = ''
		k = ''
		d = ''
		for i in sorted(dr.keys()):
			if ord(i) <= ord(s[0]):
				k += i * dr[i]
			else:
				d += i * dr[i]
			if ord(i) < ord(s[0]):
				l += i * dr[i]
			else:
				t += i * dr[i]
		if l + s + t > k + s + d:
			print(k + s + d)
		else:
			print(l + s + t)


from collections import Counter
import itertools

def ans(s, r):
	r = list(r)
	ds = Counter(s)
	dr = Counter(r)
	dr.subtract(ds)
	lst = list(dr.keys())
	for v in lst:
		if dr[v] < 0:
			return 'Impossible'
		elif dr[v] == 0:
			del dr[v]
	left = []
	right = []
	middle = []
	for i in dr:
		if i > s[0]:
			right.append(i * dr[i])
		elif i == s[0]:
			middle.append(i * dr[i])
		else:
			left.append(i * dr[i])
	left = ''.join(sorted(left))
	right = ''.join(sorted(right))
	middle = ''.join(middle)
	return left + min(middle + s, s + middle) + right
for _ in range(int(input())):
	s = input()
	r = input()
	print(ans(s, r))


from collections import Counter
from itertools import chain, starmap
from operator import mul
t = int(input())
for _ in range(t):
	s = input()
	c = Counter(input())
	c.subtract(s)
	if any((v < 0 for v in c.values())):
		print('Impossible')
	else:
		r = chain(filter(None, starmap(mul, c.items())), [s])
		r = sorted(r, key=lambda x: x[0] + (x.lstrip(x[0]) or x)[0])
		print(''.join(r))


import collections
import itertools
t = int(input())
for _ in range(t):
	s = input()
	c = collections.Counter(input())
	c.subtract(s)
	if any((v < 0 for v in c.values())):
		print('Impossible')
	else:
		r = itertools.chain(c.elements(), [s])
		r = sorted(r, key=lambda x: x[0] + (x.lstrip(x[0]) or x)[0])
		print(''.join(r))


from collections import Counter
from heapq import merge
t = int(input())
for _ in range(t):
	s = input()
	c = Counter(input())
	c.subtract(s)
	if any((v < 0 for v in c.values())):
		print('Impossible')
	else:
		r = merge(sorted(c.elements()), [s], key=lambda x: x[0] + (x.lstrip(x[0]) + x[0])[0])
		print(''.join(r))


t = int(input())
for _ in range(t):
	x = [0] * 26
	y = [0] * 26
	s = input()
	r = input()
	if len(r) < len(s):
		print('Impossible')
	else:
		i = set(s)
		j = set(r)
		for m in i:
			x[ord(m) - 97] = s.count(m)
		for m in j:
			y[ord(m) - 97] = r.count(m)
		for i in range(26):
			if y[i] < x[i]:
				print('Impossible')
				break
			else:
				y[i] = y[i] - x[i]
		else:
			l = ''
			r = ''
			if s < s[0] * len(s):
				i = ord(s[0]) - 97
				for m in range(i):
					for j in range(y[m]):
						l += chr(m + 97)
				for m in range(i, 26):
					for j in range(y[m]):
						r += chr(m + 97)
			else:
				i = ord(s[0]) - 97
				for m in range(i + 1):
					for j in range(y[m]):
						l += chr(m + 97)
				for m in range(i + 1, 26):
					for j in range(y[m]):
						r += chr(m + 97)
			print(l + s + r)


from collections import Counter
from bisect import bisect_left
t = int(input())
for _ in range(t):
	s = input()
	c = Counter(input())
	c.subtract(s)
	if any((v < 0 for v in c.values())):
		print('Impossible')
	else:
		e = sorted(c.elements())
		r = s[0]
		if (s.lstrip(r) + r)[0] >= r:
			r = chr(ord(r) + 1)
		e.insert(bisect_left(e, r), s)
		print(''.join(e))


from collections import Counter
t = int(input())
for _ in range(t):
	s = input()
	c = Counter(sorted(input()))
	c.subtract(s)
	if any((v < 0 for v in c.values())):
		print('Impossible')
	else:
		r = s[0]
		t = s.lstrip(r) + r
		if t[0] >= r:
			r = chr(ord(r) + 1)
		a = ''.join((x for x in c.elements() if x < r))
		b = ''.join((x for x in c.elements() if x >= r))
		print(a + s + b)


from collections import Counter
t = int(input())
for _ in range(t):
	s = input()
	c = Counter(map(ord, input()))
	c.subtract(map(ord, s))
	if any((v < 0 for v in c.values())):
		print('Impossible')
	else:
		t = s.lstrip(s[0])
		r = ord(s[0]) + (not t or t[0] >= s[0])
		a = ''.join((c[i] * chr(i) for i in range(ord('a'), r)))
		b = ''.join((c[i] * chr(i) for i in range(r, ord('z') + 1)))
		print(a + s + b)


for i in range(int(input())):
	S = input()
	R = input()
	l1 = [0] * 26
	l2 = [0] * 26
	T = ''
	flag = True
	for j in R:
		l1[ord(j) - 97] += 1
	for j in S:
		l2[ord(j) - 97] += 1
	for j in range(26):
		if l1[j] >= l2[j]:
			l1[j] = l1[j] - l2[j]
		else:
			flag = False
			print('Impossible')
			break
	if flag == True:
		k = 0
		for j in range(26):
			if j == ord(S[0]) - 97 and len(S) > 1 and (k == 0):
				for l in S:
					if ord(l) - 97 < j:
						T += S + l1[j] * chr(j + 97)
						k = 1
						flag = False
						break
					elif ord(l) - 97 > j:
						T += l1[j] * chr(j + 97) + S
						flag = False
						k = 1
						break
				if flag == True:
					T += S + l1[j] * chr(j + 97)
					k = 1
			elif j > ord(S[0]) - 97 and k == 0:
				T += S + l1[j] * chr(j + 97)
				k = 1
			else:
				T += l1[j] * chr(j + 97)
		if k == 0:
			T += S
		print(T)


from collections import defaultdict as dc
import sys
import math

def inp():
	p = sys.stdin.readline()
	return p
for _ in range(int(inp())):
	a = str(input())
	b = str(input())
	p = dc(int)
	for i in range(len(a)):
		p[a[i]] += 1
	z = ''
	for i in range(len(b)):
		if p[b[i]] != 0:
			p[b[i]] -= 1
		else:
			z = z + b[i]
	l = list(set(p.values()))
	if len(l) == 1 and l[0] == 0:
		q = list(z)
		q.sort()
		h = ''.join(q)
		best = a + h
		for i in range(len(h) + 1):
			c = h[:i] + a + h[i:]
			if best > c:
				best = c
		print(best)
	else:
		print('Impossible')


t = int(input())
for _ in range(t):
	s = input()
	r = input()
	found = 0
	brr = [0 for i in range(26)]
	for letter in r:
		brr[ord(letter) - ord('a')] += 1
	for letter in s:
		if brr[ord(letter) - ord('a')] == 0:
			found = 1
			break
		brr[ord(letter) - ord('a')] -= 1
	if found == 1:
		print('Impossible')
		continue
	r = ''
	for i in range(26):
		if brr[i] > 0:
			c = chr(i + ord('a'))
			r = r + c * brr[i]
	res = r + s
	if s + r < res:
		res = s + r
	for i in range(0, len(r)):
		if res > r[0:i] + s + r[i:]:
			res = r[0:i] + s + r[i:]
	print(res)


t = int(input())
from itertools import permutations
for _ in range(t):
	s = input()
	r = input()
	d = {}
	for i in r:
		try:
			d[i] += 1
		except:
			d[i] = 1
	k = ''
	flag = True
	for i in s:
		try:
			if d[i] == 0:
				flag = False
				break
			k += i
			d[i] -= 1
		except:
			flag = False
			break
	if flag == False:
		print('Impossible')
		continue
	a1 = ''
	a2 = ''
	for i in d.keys():
		if i < k[0]:
			a1 += i * d[i]
			a2 += i * d[i]
			d[i] = 0
		elif i == k[0]:
			a2 += i * d[i]
	b1 = ''
	b2 = ''
	for i in d.keys():
		if i == k[0]:
			b1 += i * d[i]
		else:
			b1 += i * d[i]
			b2 += i * d[i]
	ans = ''.join(sorted(a1)) + k + ''.join(sorted(b1))
	ans1 = ''.join(sorted(a2)) + k + ''.join(sorted(b2))
	print(min(ans1, ans))


t = int(input())
while t > 0:
	s = input()
	r = input()
	li = ord(s[0]) - 97
	cnt = [0 for i in range(27)]
	ans = ''
	for i in range(len(r)):
		ind = ord(r[i]) - 97
		cnt[ind] += 1
	for i in range(len(s)):
		ind = ord(s[i]) - 97
		cnt[ind] -= 1
		if cnt[ind] < 0:
			ans = 'IMPOSSIBLE'
	if ans == 'IMPOSSIBLE':
		print('Impossible')
	else:
		for i in range(len(cnt)):
			if i != li and cnt[i] > 0:
				ans += chr(i + 97) * cnt[i]
			if i == li:
				nb = False
				for j in range(1, len(s)):
					if s[0] > s[j]:
						nb = True
						break
					if s[0] < s[j]:
						break
				if nb:
					ans += s
					ans += chr(i + 97) * cnt[i]
				else:
					ans += chr(i + 97) * cnt[i]
					ans += s
		print(ans)
	t -= 1


def ii():
	return int(input())

def fi():
	return float(input())

def si():
	return input()

def mi():
	return map(int, input().split())

def li():
	return list(mi())
import math
from collections import Counter
t = ii()
for i in range(t):
	x = si().rstrip()
	y = si().rstrip()
	d = {}
	for i in y:
		if i in d:
			d[i] += 1
		else:
			d[i] = 1
	a = 0
	for i in x:
		if i not in d or d[i] == 0:
			print('Impossible')
			a = 1
			break
		else:
			d[i] -= 1
	if a == 0:
		s = ''
		ans = 0
		for i in sorted(d.keys()):
			k = i * d[i]
			if i >= x[0] and ans == 0:
				s += min(x + k, k + x)
				ans = 1
			else:
				s += k
		if ans == 0:
			s += x
		print(s)


from collections import Counter

def sol(a, b):
	ad = dict(Counter(a))
	bd = dict(Counter(b))
	for i in ad:
		if i in bd and bd[i] >= ad[i]:
			bd[i] -= ad[i]
			if bd[i] == 0:
				del bd[i]
		else:
			return 'Impossible'
	l = []
	r = []
	if a < a[0] * len(a):
		for i in sorted(bd):
			if i < a[0]:
				l.append(i * bd[i])
			else:
				r.append(i * bd[i])
	else:
		for i in sorted(bd):
			if i <= a[0]:
				l.append(i * bd[i])
			else:
				r.append(i * bd[i])
	return ''.join(l) + a + ''.join(r)
for _ in range(int(input())):
	a = input()
	b = input()
	print(sol(a, b))


def sol(a, b):
	ad = {}
	bd = {}
	for i in a:
		if i in ad:
			ad[i] += 1
		else:
			ad[i] = 1
	for i in b:
		if i in bd:
			bd[i] += 1
		else:
			bd[i] = 1
	for i in ad:
		if i in bd and bd[i] >= ad[i]:
			bd[i] -= ad[i]
			if bd[i] == 0:
				del bd[i]
		else:
			return 'Impossible'
	l = []
	r = []
	if a < a[0] * len(a):
		for i in sorted(bd):
			if i < a[0]:
				l.append(i * bd[i])
			else:
				r.append(i * bd[i])
	else:
		for i in sorted(bd):
			if i <= a[0]:
				l.append(i * bd[i])
			else:
				r.append(i * bd[i])
	res = l + list(a) + r
	return ''.join(res)
for _ in range(int(input())):
	a = input()
	b = input()
	print(sol(a, b))


t = int(input())
for _ in range(t):
	s = input()
	r = input()
	d1 = {}
	d2 = {}
	for i in s:
		try:
			d1[i] += 1
		except:
			d1[i] = 1
	for i in r:
		try:
			d2[i] += 1
		except:
			d2[i] = 1
	f = True
	g = True
	j = True
	l = 0
	for i in list(d1.keys()):
		if l > 0 and s[l] != s[l - 1] and g:
			j = s[l] < s[l - 1]
			g = False
		l += 1
		try:
			if d1[i] > d2[i]:
				f = False
				print('Impossible')
				break
			else:
				d2[i] -= d1[i]
		except:
			f = False
			print('Impossible')
			break
	if f:
		a = sorted(list(d2.keys()))
		h = ''
		for k in a:
			for _ in range(d2[k]):
				h += k
		m = s + h
		for i in range(1, len(h) + 1):
			temp = h[:i] + s + h[i:]
			if temp < m:
				m = temp
		print(m)


t = int(input())
for _ in range(t):
	s = input()
	r = input()
	rtem = r
	for i in s:
		x = rtem.find(i)
		if x == -1:
			print('Impossible', end='')
			break
		rtem = rtem[:x] + rtem[x + 1:]
	rtem = ''.join(sorted(rtem))
	y = s[0]
	se = s[0]
	for i in range(len(s) - 1):
		if s[i] != s[i + 1]:
			se = s[i + 1]
			break
	if x != -1:
		if se > y:
			pr = False
			for i in rtem:
				if i <= y:
					print(i, end='')
				else:
					if not pr:
						print(s, end='')
						pr = True
					print(i, end='')
			if not pr:
				print(s, end='')
		else:
			pr = False
			for i in rtem:
				if i < y:
					print(i, end='')
				else:
					if not pr:
						print(s, end='')
						pr = True
					print(i, end='')
			if not pr:
				print(s, end='')
	print()


for _ in range(int(input())):
	s = input()
	r = input()
	temp = [0] * 26
	flag = 1
	for i in r:
		temp[ord(i) - 97] += 1
	for i in s:
		if temp[ord(i) - 97] == 0:
			flag = 0
			break
		temp[ord(i) - 97] -= 1
	if flag:
		s1 = ''
		for i in range(26):
			for j in range(temp[i]):
				s1 += chr(i + 97)
		l = len(s1)
		if l == 0:
			print(s)
		for i in range(l):
			if s[0] == s1[i] and s < s1[i] * len(s):
				print(s1[:i] + s + s1[i:])
				break
			elif s[0] < s1[i]:
				print(s1[:i] + s + s1[i:])
				break
			elif i == l - 1:
				print(s1 + s)
	else:
		print('Impossible')


for t in range(int(input())):
	s = input().strip()
	r = input().strip()
	freq = [0 for i in range(26)]
	for i in range(len(r)):
		freq[ord(r[i]) - 97] += 1
	for i in range(len(s)):
		freq[ord(s[i]) - 97] -= 1
	poss = True
	for i in range(26):
		if freq[i] < 0:
			poss = False
			break
	if poss:
		ans = ''
		ind = ord(s[0]) - 97
		for i in range(ind):
			ans += chr(97 + i) * freq[i]
		is_next_big = True
		for i in range(1, len(s)):
			if s[0] > s[i]:
				is_next_big = False
				break
			elif s[0] < s[i]:
				break
		if is_next_big:
			ans += chr(97 + ind) * freq[ind]
			ans += s
		else:
			ans += s
			ans += chr(97 + ind) * freq[ind]
		for i in range(ind + 1, 26):
			ans += chr(97 + i) * freq[i]
		print(ans)
	else:
		print('Impossible')


from collections import Counter
t = int(input())
for _ in range(t):
	S = input()
	R = input()
	S1 = dict(Counter(S))
	R1 = dict(Counter(R))
	check = 1
	for (i, j) in S1.items():
		if R1.get(i, 0) < j:
			check = 0
			break
	if check:
		Q = dict()
		for (i, j) in R1.items():
			if j - S1.get(i, 0) > 0:
				Q[i] = j - S1.get(i, 0)
		(left, right) = ([], [])
		if S < S[0] * len(S):
			for (i, j) in Q.items():
				if i < S[0]:
					left.append(i * j)
				else:
					right.append(i * j)
		else:
			for (i, j) in Q.items():
				if i <= S[0]:
					left.append(i * j)
				else:
					right.append(i * j)
		left = sorted(left)
		left = ''.join(left)
		right = sorted(right)
		right = ''.join(right)
		final = left + S + right
		print(final)
	else:
		print('Impossible')


t = int(input())
for _ in range(t):
	x = input().rstrip()
	y = input().rstrip()
	d = {}
	for i in y:
		if i in d:
			d[i] += 1
		else:
			d[i] = 1
	a = False
	for i in x:
		if i not in d or d[i] == 0:
			print('Impossible')
			a = True
			break
		else:
			d[i] -= 1
	if a == False:
		s = ''
		ans = False
		for i in sorted(d.keys()):
			k = i * d[i]
			if i >= x[0] and ans == False:
				s += min(x + k, k + x)
				ans = True
			else:
				s += k
		if ans == False:
			s += x
		print(s)


T = int(input())
t = 0
while t < T:
	t += 1
	S = input()
	R = input()
	dic = {}
	for c in R:
		if c not in list(dic.keys()):
			dic[c] = 1
		else:
			dic[c] += 1
	res = ''
	f = 1
	for c in S:
		if c in list(dic.keys()) and dic[c] >= 1:
			res += c
			dic[c] -= 1
		else:
			f = 0
			break
	alp = 'abcdefghijklmnopqrstuvwxyz'
	if f == 0:
		print('Impossible')
		continue
	temp = res[0]
	need = ''
	for c in res:
		if c != temp:
			need = c
			break
	if need == '':
		need = temp
	temp = ord(temp)
	res2 = ''
	for c in alp:
		if c in list(dic.keys()) and ord(c) < temp:
			x = dic[c]
			for i in range(x):
				res2 = res2 + c
		elif c in list(dic.keys()) and ord(c) == temp:
			x = dic[c]
			while ord(c) <= ord(need) and x > 0:
				res2 += c
				x -= 1
			for i in range(x):
				res = res + c
		elif c in list(dic.keys()) and ord(c) >= temp:
			x = dic[c]
			for i in range(x):
				res = res + c
	res = res2 + res
	print(res)


t = int(input())
for ankit in range(t):
	a = input()
	b = input()
	p = [0] * 26
	q = [0] * 26
	f = 0
	for i in a:
		p[ord(i) - 97] += 1
	for i in b:
		q[ord(i) - 97] += 1
	for i in range(26):
		if p[i] > q[i]:
			f = 1
			break
		q[i] -= p[i]
	if f == 1:
		print('Impossible')
	else:
		for i in range(ord(a[0]) - 97):
			s = q[i]
			while s > 0:
				print(chr(i + 97), end='')
				s -= 1
		s = 0
		oo = len(a)
		r = 0
		while s < oo - 1:
			if a[s] != a[s + 1]:
				if a[s] > a[s + 1]:
					r = 0
				else:
					r = 1
				break
			s += 1
		if r == 0:
			print(a, end='')
			for i in range(ord(a[0]) - 97, 26):
				s = q[i]
				while s > 0:
					print(chr(i + 97), end='')
					s -= 1
		else:
			s = q[ord(a[0]) - 97]
			while s > 0:
				print(a[0], end='')
				s -= 1
			print(a, end='')
			for i in range(ord(a[0]) - 97 + 1, 26):
				s = q[i]
				while s > 0:
					print(chr(i + 97), end='')
					s -= 1
		print()


t = int(input())
for i in range(t):
	s = input()
	r = input()
	flag = 0
	sn = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
	rn = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
	for j in range(len(s)):
		sn[ord(s[j]) - 97] += 1
	for j in range(len(r)):
		rn[ord(r[j]) - 97] += 1
	for j in range(26):
		if rn[j] < sn[j]:
			flag = 1
			break
	if flag == 1:
		print('Impossible')
	else:
		left1 = ''
		left2 = ''
		ans = ''
		for j in range(26):
			rn[j] = rn[j] - sn[j]
			if j < ord(s[0]) - 97:
				left1 = left1 + rn[j] * chr(j + 97)
			elif j > ord(s[0]) - 97:
				left2 = left2 + rn[j] * chr(j + 97)
		print(min(left1 + s + rn[ord(s[0]) - 97] * s[0] + left2, left1 + rn[ord(s[0]) - 97] * s[0] + s + left2))


import io, sys, atexit, os
import math as ma
from sys import exit
from decimal import Decimal as dec
from itertools import permutations
from itertools import combinations

def li():
	return list(map(int, sys.stdin.readline().split()))

def num():
	return map(int, sys.stdin.readline().split())

def nu():
	return int(input())

def find_gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x

def lcm(x, y):
	gg = find_gcd(x, y)
	return x * y // gg
mm = 1000000007

def solve():
	t = nu()
	for tt in range(t):
		s = input()
		r = input()
		ff = [0] * 26
		gg = [0] * 26
		for i in range(len(s)):
			ff[ord(s[i]) - ord('a')] += 1
		for i in range(len(r)):
			gg[ord(r[i]) - ord('a')] += 1
		fl = True
		for i in range(26):
			if ff[i] > gg[i]:
				fl = False
				break
			gg[i] -= ff[i]
		if fl == False:
			print('Impossible')
		elif len(s) == 1:
			xp = s[0]
			for i in range(ord(s[0]) - ord('a'), -1, -1):
				if gg[i] == 0:
					continue
				pq = chr(i + 97)
				for j in range(gg[i]):
					xp = pq + xp
			for i in range(ord(s[0]) - ord('a') + 1, 26):
				if gg[i] == 0:
					continue
				pq = chr(i + 97)
				for j in range(gg[i]):
					xp = xp + pq
			print(xp)
		else:
			ind = -1
			lp = 1
			for i in range(len(s) - 1):
				if s[i] != s[i + 1]:
					ind = i
					break
			if ind != -1:
				if s[ind] < s[ind + 1]:
					lp = -1
			if lp == 1:
				xp = s
				pq = chr(97 + ord(s[0]) - ord('a'))
				for i in range(gg[ord(s[0]) - ord('a')]):
					xp = xp + pq
				for i in range(ord(s[0]) - ord('a') - 1, -1, -1):
					if gg[i] == 0:
						continue
					pq = chr(i + 97)
					for j in range(gg[i]):
						xp = pq + xp
				for i in range(ord(s[0]) - ord('a') + 1, 26):
					if gg[i] == 0:
						continue
					pq = chr(i + 97)
					for j in range(gg[i]):
						xp = xp + pq
				print(xp)
			else:
				xp = ''
				for i in range(ord(s[0]) - ord('a'), -1, -1):
					if gg[i] == 0:
						continue
					pq = chr(i + 97)
					for j in range(gg[i]):
						xp = pq + xp
				xp = xp + s
				for i in range(ord(s[0]) - ord('a') + 1, 26):
					if gg[i] == 0:
						continue
					pq = chr(i + 97)
					for j in range(gg[i]):
						xp = xp + pq
				print(xp)
solve()


def reo(s, r):
	s1 = [0 for i in range(26)]
	r1 = [0 for i in range(26)]
	for i in s:
		s1[ord(i) - 97] += 1
	for i in r:
		r1[ord(i) - 97] += 1
	flag = 0
	flag1 = 0
	for i in range(len(s) - 1):
		if s[i] > s[i + 1]:
			flag1 = 1
			break
		if s[i] == s[i + 1]:
			continue
		break
	for i in range(26):
		if s1[i] > r1[i]:
			flag = 1
			print('Impossible')
			break
		r1[i] -= s1[i]
	if flag != 1:
		re = ord(s[0]) - 97
		if flag1 == 1:
			re -= 1
		for i in range(re + 1):
			print(chr(97 + i) * r1[i], end='')
		print(s, end='')
		for i in range(re + 1, 26):
			print(chr(97 + i) * r1[i], end='')
		print()
t = int(input())
while t:
	t -= 1
	s = input().rstrip()
	r = input().rstrip()
	reo(s, r)


from collections import defaultdict
from bisect import bisect_left, bisect_right

def bin_Search(arr, c):
	s = 0
	e = len(arr)
	flag = 0
	while s <= e:
		mid = (s + e) // 2
		if mid == len(arr):
			break
		if arr[mid] == c:
			flag = 1
			break
		elif arr[mid] > c:
			e = mid - 1
		else:
			s = mid + 1
	if flag == 0:
		return mid
	else:
		return -1
t = int(input())
for i in range(t):
	s = input()
	r = input()
	ds = defaultdict(int)
	dr = defaultdict(int)
	for x in s:
		ds[x] += 1
	for x in r:
		dr[x] += 1
	flag = 0
	for x in ds:
		if ds[x] > dr[x]:
			flag = 1
			break
		else:
			dr[x] -= ds[x]
	if flag == 1:
		print('Impossible')
		continue
	newr = []
	for x in dr:
		newr += [x] * dr[x]
	newr.sort()
	kek = ''
	for x in newr:
		kek += x
	if s[0] not in newr:
		lol = bisect_right(newr, s[0], 0, len(newr))
		print(kek[:lol] + s + kek[lol:])
	else:
		right = bisect_right(newr, s[0], 0, len(newr))
		left = bisect_left(newr, s[0], 0, len(newr))
		leftans = kek[:left] + s + kek[left:]
		rightans = kek[:right] + s + kek[right:]
		print(min(leftans, rightans))


import bisect

class Solution(object):

	def __init__(self):
		pass

	def sol(self, S, R):
		mp = {}
		for ch in R:
			if ch not in mp:
				mp[ch] = 0
			mp[ch] += 1
		for ch in S:
			if ch not in mp:
				return (False, None)
			if mp[ch] == 0:
				return (False, None)
			mp[ch] -= 1
		_R = ''
		keys = sorted(mp.keys())
		for e in keys:
			_R += e * mp[e]
		best = S + _R
		for i in range(1, len(_R) + 1):
			c = _R[0:i] + S + _R[i:]
			if best > c:
				best = c
		return (True, best)

def main():
	T = int(input())
	sol = Solution()
	for i in range(0, T):
		S = input()
		R = input()
		rs = sol.sol(S, R)
		if not rs[0]:
			print('Impossible')
			continue
		print(rs[1])
	return 0
main()


mod = 1000000007
MOD = 998244353
ii = lambda : int(input())
si = lambda : input()
dgl = lambda : list(map(int, input()))
f = lambda : map(int, input().split())
il = lambda : list(map(int, input().split()))
it = lambda : tuple(map(int, input().split()))
ls = lambda : list(input())
for _ in range(ii()):
	s = si()
	r = si()
	l = [0] * 26
	for i in r:
		l[ord(i) - ord('a')] += 1
	fg = 1
	for i in s:
		if l[ord(i) - ord('a')] <= 0:
			print('Impossible')
			fg = 0
			break
		else:
			l[ord(i) - ord('a')] -= 1
	if fg:
		ind = 0
		for i in range(1, len(s)):
			if s[i] != s[i - 1]:
				ind = i
				break
		if s[0] > s[ind]:
			x = ''
			for i in range(26):
				if chr(i + ord('a')) < s[0]:
					x += chr(i + ord('a')) * l[i]
			x += s
			for i in range(26):
				if chr(i + ord('a')) >= s[0]:
					x += chr(i + ord('a')) * l[i]
			print(x)
		else:
			x = ''
			for i in range(26):
				if chr(i + ord('a')) <= s[0]:
					x += chr(i + ord('a')) * l[i]
			x += s
			for i in range(26):
				if chr(i + ord('a')) > s[0]:
					x += chr(i + ord('a')) * l[i]
			print(x)


import bisect
t = int(input())
so = 'abcdefghijklmnopqrstuvwxyz'
sp = {}
j = 0
for i in so:
	sp[i] = j
	j += 1
for _ in range(t):
	aa = input()
	bb = input()
	a = []
	for i in aa:
		a.append(sp[i])
	b = []
	for i in bb:
		b.append(sp[i])
	if len(a) > len(b):
		print('Impossible')
		continue
	ss = {}
	j = 0
	for i in b:
		try:
			ss[i][0].append(j)
		except:
			ss[i] = [[j], 0]
		j += 1
	vis = [0] * len(b)
	st = False
	for i in a:
		try:
			aa = ss[i]
			if ss[i][1] == len(ss[i][0]):
				st = True
				break
			ss[i][1] += 1
			vis[ss[i][0][ss[i][1] - 1]] = 1
		except:
			st = True
			break
	if st:
		print('Impossible')
		continue
	tot = a
	tot2 = []
	for i in range(len(b)):
		if vis[i] == 0:
			tot2.append(b[i])
	tot2.sort()
	ind = bisect.bisect_left(tot2, a[0])
	try:
		if tot2[ind] == a[0]:
			st = False
			for i in a[1:]:
				if i < a[0]:
					st = True
					break
				if i > a[0]:
					break
			if st:
				ans = tot2[:ind] + a + tot2[ind:]
			else:
				ind2 = bisect.bisect_right(tot2, a[0])
				ans = tot2[:ind2] + a + tot2[ind2:]
		else:
			ans = tot2[:ind] + a + tot2[ind:]
	except:
		ans = tot2[:ind] + a + tot2[ind:]
	print(''.join([so[i] for i in ans]))


for _ in range(int(input())):
	a = input()
	b = input()
	d1 = {}
	d2 = {}
	for j in range(97, 97 + 26):
		d1[chr(j)] = 0
		d2[chr(j)] = 0
	for i in a:
		d1[i] += 1
	for i in b:
		d2[i] += 1
	z = 0
	for i in range(97, 97 + 26):
		i = chr(i)
		if d2[i] < d1[i]:
			z = 1
			break
	if z == 1:
		print('Impossible')
	else:
		r = []
		le = 0
		for i in range(97, 97 + 26):
			i = chr(i)
			for j in range(d2[i] - d1[i]):
				r.append(i)
				le += 1
		r.sort()
		z = 0
		for j in range(1, len(a)):
			if a[0] < a[j]:
				z = 0
				break
			elif a[0] > a[j]:
				z = 1
				break
			if j == len(a) - 1:
				z = 1
		p22 = 0
		for q in range(le):
			i = r[q]
			if i < a[0]:
				print(i, end='')
			elif i == a[0] and z == 0:
				print(i, end='')
			else:
				p22 = 1
				print(a, end='')
				for j in range(q, le - 1):
					print(r[j], end='')
				print(r[-1])
				break
		if p22 == 0:
			print(a)


from bisect import *
from collections import *
from itertools import *
import functools
import sys
import math
from decimal import *
from copy import *
from heapq import *
getcontext().prec = 30
MAX = sys.maxsize
MAXN = 4000010
MOD = 10 ** 9 + 7
spf = [i for i in range(MAXN)]

def sieve():
	for i in range(2, MAXN, 2):
		spf[i] = 2
	for i in range(3, int(MAXN ** 0.5) + 1):
		if spf[i] == i:
			for j in range(i * i, MAXN, i):
				if spf[j] == j:
					spf[j] = i

def mhd(a, b):
	return abs(a[0] - b[0]) + abs(b[1] - a[1])

def charIN(x=' '):
	return sys.stdin.readline().strip().split(x)

def arrIN(x=' '):
	return list(map(int, sys.stdin.readline().strip().split(x)))

def eld(x, y):
	a = y[0] - x[0]
	b = x[1] - y[1]
	return (a * a + b * b) ** 0.5

def lgcd(a):
	g = a[0]
	for i in range(1, len(a)):
		g = math.gcd(g, a[i])
	return g

def ms(a):
	msf = -MAX
	meh = 0
	st = en = be = 0
	for i in range(len(a)):
		meh += a[i]
		if msf < meh:
			msf = meh
			st = be
			en = i
		if meh < 0:
			meh = 0
			be = i + 1
	return (msf, st, en)

def ncr(n, r):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % MOD
		den = den * (i + 1) % MOD
	return num * pow(den, MOD - 2, MOD) % MOD

def flush():
	return sys.stdout.flush()
for _ in range(int(input())):
	s = input().strip()
	r = input().strip()
	cs = Counter(s)
	cr = Counter(r)
	for i in cs.keys():
		if cs[i] > cr[i]:
			print('Impossible')
			break
	else:
		ans = s
		for i in s:
			cr[i] -= 1
		x = ''
		for i in cr.keys():
			x += i * cr[i]
		x = ''.join(sorted(x))
		mn = ans + x
		for i in range(1, len(x) + 1):
			mn = min(mn, x[:i] + ans + x[i:])
		print(mn)


from sys import stdin, stdout
import heapq
import cProfile, math
from collections import Counter, defaultdict, deque
from bisect import bisect_left, bisect, bisect_right
import itertools
from copy import deepcopy
from fractions import Fraction
import sys, threading
import operator as op
from functools import reduce
import sys
sys.setrecursionlimit(10 ** 6)
threading.stack_size(2 ** 27)
fac_warm_up = False
printHeap = str()
memory_constrained = False
P = 10 ** 9 + 7

class MergeFind:

	def __init__(self, n):
		self.parent = list(range(n))
		self.size = [1] * n
		self.num_sets = n
		self.lista = [[_] for _ in range(n)]

	def find(self, a):
		to_update = []
		while a != self.parent[a]:
			to_update.append(a)
			a = self.parent[a]
		for b in to_update:
			self.parent[b] = a
		return self.parent[a]

	def merge(self, a, b):
		a = self.find(a)
		b = self.find(b)
		if a == b:
			return
		if self.size[a] < self.size[b]:
			(a, b) = (b, a)
		self.num_sets -= 1
		self.parent[b] = a
		self.size[a] += self.size[b]
		self.lista[a] += self.lista[b]

	def set_size(self, a):
		return self.size[self.find(a)]

	def __len__(self):
		return self.num_sets

def display(string_to_print):
	stdout.write(str(string_to_print) + '\n')

def prime_factors(n):
	factors = dict()
	for i in range(2, math.ceil(math.sqrt(n)) + 1):
		while n % i == 0:
			if i in factors:
				factors[i] += 1
			else:
				factors[i] = 1
			n = n // i
	if n > 2:
		factors[n] = 1
	return factors

def all_factors(n):
	return set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0)))

def fibonacci_modP(n, MOD):
	if n < 2:
		return 1
	return (cached_fn(fibonacci_modP, (n + 1) // 2, MOD) * cached_fn(fibonacci_modP, n // 2, MOD) + cached_fn(fibonacci_modP, (n - 1) // 2, MOD) * cached_fn(fibonacci_modP, (n - 2) // 2, MOD)) % MOD

def factorial_modP_Wilson(n, p):
	if p <= n:
		return 0
	res = p - 1
	for i in range(n + 1, p):
		res = res * cached_fn(InverseEuler, i, p) % p
	return res

def binary(n, digits=20):
	b = bin(n)[2:]
	b = '0' * (digits - len(b)) + b
	return b

def is_prime(n):
	if n < 4:
		return True
	if n % 2 == 0:
		return False
	if n % 3 == 0:
		return False
	i = 5
	w = 2
	while i * i <= n:
		if n % i == 0:
			return False
		i += w
		w = 6 - w
	return True

def generate_primes(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p]:
			for i in range(p * 2, n + 1, p):
				prime[i] = False
		p += 1
	return prime
factorial_modP = []

def warm_up_fac(MOD):
	global factorial_modP, fac_warm_up
	if fac_warm_up:
		return
	factorial_modP = [1 for _ in range(fac_warm_up_size + 1)]
	for i in range(2, fac_warm_up_size):
		factorial_modP[i] = factorial_modP[i - 1] * i % MOD
	fac_warm_up = True

def InverseEuler(n, MOD):
	return pow(n, MOD - 2, MOD)

def nCr(n, r, MOD):
	global fac_warm_up, factorial_modP
	if not fac_warm_up:
		warm_up_fac(MOD)
		fac_warm_up = True
	return factorial_modP[n] * (pow(factorial_modP[r], MOD - 2, MOD) * pow(factorial_modP[n - r], MOD - 2, MOD) % MOD) % MOD

def get_int():
	return int(stdin.readline().strip())

def get_tuple():
	return map(int, stdin.readline().split())

def get_list():
	return list(map(int, stdin.readline().split()))
memory = dict()

def clear_cache():
	global memory
	memory = dict()

def cached_fn(fn, *args):
	global memory
	if args in memory:
		return memory[args]
	else:
		result = fn(*args)
		memory[args] = result
		return result

def ncr(n, r):
	return math.factorial(n) / (math.factorial(n - r) * math.factorial(r))

def binary_search(i, li):
	fn = lambda x: li[x] - x // i
	x = -1
	b = len(li)
	while b >= 1:
		while b + x < len(li) and fn(b + x) > 0:
			x += b
		b = b // 2
	return x
TestCases = True
optimise_for_recursion = True

def is_inc_st(st):
	prev = st[0]
	for i in st:
		if i < prev:
			return False
		elif i > prev:
			return True
	return True

def main():
	st = list(stdin.readline().strip())
	rt = list(stdin.readline().strip())
	cnt = Counter(rt)
	for i in st:
		if i in cnt and cnt[i] > 0:
			cnt[i] -= 1
		else:
			print('Impossible')
			return
	res = []
	for chr in sorted(cnt.keys()):
		if chr == st[0]:
			if is_inc_st(st):
				res += [chr] * cnt[chr]
				res += st
			else:
				res += st
				res += [chr] * cnt[chr]
		else:
			res += [chr] * cnt[chr]
	print(''.join(res))
if TestCases:
	for i in range(get_int()):
		main()
else:
	main() if not optimise_for_recursion else threading.Thread(target=main).start()


T = int(input())
while T:
	S = input()
	R = input()
	flag = True
	a = [0 for i in range(26)]
	for i in range(26):
		if S.count(chr(97 + i)) > R.count(chr(97 + i)):
			flag = False
		else:
			a[i] = R.count(chr(97 + i)) - S.count(chr(97 + i))
	if flag:
		b = ord(S[0]) - 97
		c = ''
		f1 = True
		for i in range(len(S)):
			if S[i] > S[0]:
				break
			if S[i] < S[0]:
				f1 = False
				break
		i = 0
		if f1:
			while i <= b:
				c += chr(i + 97) * a[i]
				i += 1
			c += S
			while i < 26:
				c += chr(i + 97) * a[i]
				i += 1
		else:
			while i < b:
				c += chr(i + 97) * a[i]
				i += 1
			c += S
			while i < 26:
				c += chr(i + 97) * a[i]
				i += 1
		print(c)
	else:
		print('Impossible')
	T -= 1


from collections import Counter

def compareCounter(c1, c2):
	for char in c1:
		if char not in c2:
			return False
		elif c1[char] > c2[char]:
			return False
	return True

def getOrder(s):
	i = 1
	order = True
	while i < len(s) and s[i] == s[i - 1]:
		i += 1
	if i >= len(s):
		i -= 1
	if s[i] > s[0]:
		order = True
	else:
		order = False
	return order

def reduceCounter(c1, c2, s):
	order = getOrder(s)
	d = dict()
	for char in c1:
		d[char] = c2[char] - c1[char]
	for char in c2:
		if char not in c1:
			d[char] = c2[char]
	first = s[0]
	ret = ''
	chars = sorted(list(d.keys()))
	char_index = 0
	len_char_index = len(chars)
	if order:
		while char_index < len_char_index and ord(chars[char_index]) <= ord(first):
			ret += chars[char_index] * d[chars[char_index]]
			char_index += 1
		ret += ''.join(s)
		while char_index < len_char_index:
			ret += chars[char_index] * d[chars[char_index]]
			char_index += 1
		return ret
	else:
		while char_index < len_char_index and ord(chars[char_index]) < ord(first):
			ret += chars[char_index] * d[chars[char_index]]
			char_index += 1
		ret += ''.join(s)
		while char_index < len_char_index:
			ret += chars[char_index] * d[chars[char_index]]
			char_index += 1
		return ret
for _ in range(int(input())):
	s1 = list(input())
	s2 = list(input())
	c1 = Counter(s1)
	c2 = Counter(s2)
	if compareCounter(c1, c2):
		print(reduceCounter(c1, c2, s1))
	else:
		print('Impossible')


t = int(input(''))
for v in range(t):
	s = input('')
	r = input('')
	if len(r) < len(s):
		print('Impossible')
		continue
	ds = {}
	dr = {}
	ls = len(s)
	lr = len(r)
	for i in range(lr):
		if i < ls:
			if s[i] not in ds:
				ds[s[i]] = 0
			ds[s[i]] = ds[s[i]] + 1
		if r[i] not in dr:
			dr[r[i]] = 0
		dr[r[i]] = dr[r[i]] + 1
	res = True
	for k in ds:
		if k not in dr:
			res = False
			break
		elif dr[k] < ds[k]:
			res = False
			break
		else:
			dr[k] = dr[k] - ds[k]
	if not res:
		print('Impossible')
		continue
	al = []
	for i in range(97, 123, 1):
		c = chr(i)
		al.append(c)
	fr = s[0]
	ans = ''
	for c in al:
		if c in dr:
			if c != s[0]:
				ans = ans + c * dr[c]
			else:
				o1 = c * dr[c] + s
				o2 = s + c * dr[c]
				if o1 < o2:
					ans = ans + o1
				else:
					ans = ans + o2
	print(ans)