I. The Test of the Clever Pig
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Little H is a clever pig who can use artificial intelligence. Today, he is participating in the Little Pig IQ Test Contest, but he got stuck on the last problem:

  • Given two strings $$$s$$$ and $$$t$$$ consisting of lowercase letters, find the lexicographically smallest common subsequence of length $$$2$$$ between them.

A string $$$a$$$ is a subsequence of a string $$$b$$$ if and only if $$$a$$$ can be obtained from $$$b$$$ by deleting some characters (or none) without changing the relative order of the remaining characters.

Little H does not know how to solve this problem. As Little H's agent, please help him.

Input

The first line contains an integer $$$T$$$ ($$$1 \leq T \leq 2 \times 10^4$$$), representing the number of test cases.

For each test case, two strings $$$s$$$ and $$$t$$$ are given on two separate lines ($$$1 \leq |s|,|t| \leq 10^5$$$). It is guaranteed that all strings consist only of lowercase letters.

It is guaranteed that over all test cases, the sum of $$$|s|+|t|$$$ does not exceed $$$2 \times 10^5$$$. $$$|s|$$$ and $$$|t|$$$ denote the lengths of strings $$$s$$$ and $$$t$$$, respectively.

Output

For each test case, output one line containing a string representing the answer you found.

If the two strings do not have a common subsequence of length $$$2$$$, output one line containing HENG!.

Example
Input
3
azzza
zazaz
azzza
zbzbz
you
ak
Output
aa
zz
HENG!