Description

 

Big Orange Cat（大橘） loves doing puzzles. He has n types of puzzles in total, and each puzzle i can be represented by a string A_i composed of all visible characters from the ASCII code.

Unfortunately, he messed up the puzzles, what a baganono... Now for each puzzle i, he has found some puzzle pieces, represented by a string B_i. Your task is to find a way to tell Big Orange Cat from which positions in B_i he should take out puzzle pieces and rearrange them to form A_i.

However, there might be many possible ways, and since Big Orange Cat is very lazy, please output the lexicographically smallest method.

Important: The method for comparing the lexicographic order of two strings is as follows: Starting from the first position (leftmost), find the first character that differs. The string with the smaller character at that position is considered lexicographically smaller. For example, "abc" < "abd" because the first differing letter 'c' < 'd'.

Input

The first line of input contains an integer n. n represents the number of puzzle-instruction manual pairs.

The following n lines each contain two strings, A_i and B_i, separated by a space. They represent the i-th puzzle and instruction manual, respectively.

 

Constraints

• 1 ≤ n ≤ 500
• All strings are composed of uppercase and lowercase letters, and any visible symbols that can be represented by ASCII code (ASCII Codes 33 to 126)
• 1 ≤ | A_i | ≤ | B_i | ≤ 10000 (| S | represents the length of string S)

Subtasks

• Testcases 1 ~ 2: | A_i | = | B_i |, characters within A_i , B_i are arranged in ascending lexicographic order.
• Testcases 3 ~ 4: | A_i | = | B_i |
• Testcases 5 ~ 8: For each B_i, there is only one possible way, or no way at all, to create the corresponding A_i.
• Testcases 9 ~ 10: No additional restrictions.

Tips: ASCII Codes 33 ~ 126 are: !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~

Output

Output n lines, each line should be in one of the following two formats according to the situation:

1. If B_i can form A_i : Output |A_i| increasing numbers representing the answer (x₁ < x₂ < ...), separated by a space.
2. Output "baganono" (without quotation marks)

Please remember to print "\n" at the end, and dont print space (" ") at the end of every line.

hint 1: The key to finding the lexicographically smallest solution lies in Big Orange Cat's personality: laziness. Therefore, the secret is to take the smallest possible numbers.
hint 2: Try to recall how you determined whether it was possible to form the required string in homework 4.

Sample Input  Download

Sample Output  Download

Tags

Discuss