Hoang's communications platoon received a message from his superiors, however the message was encrypted. The platoon leader assigned Hoang and three other teammates, Huy, Truong and Quan, to research and decode the message.

During the process of researching the newsletter, Hoang's teammates discovered a string st capable of decoding this message. They believed that the password to decrypt this message was a certain substring st1 of the string st. The field assumes that the substring st1 is the beginning of the string st; Quan thinks that substring st1 must be the end of st and Huy thinks that substring st1 must be somewhere inside string st (that is, string st1 is neither the beginning nor the end of string st).

Hoang chose the substring t to please all his teammates. In addition, of all the variations accepted, Hoang chose the longest one. When Hoang used the chosen password to decrypt, the message was decrypted.

Please write a program to help Hoang and his teammates find the best password string to decrypt the message.

Input:

Each test contains multiple test cases.

• The first line contains a single integer t (1 ≤ t ≤ ~10^3!) — the number of test cases. Each test case consists of two lines.
• The next t lines, each lines contain a string st (1 ≤ |st| ≤ 20000), consisting of only lowercase latin letters.

Output:

Each testcase prints on 1 line, each line contains a string st1 if a suitable decryption password is found. If it does not exist, print the string "Just a legend".

Example

Input

2
fixprefixsuffix
abcdabc

Output

fix
Just a legend