You are given two strings S1, S2 of not more than 250 characters each. S1 does not contain characters ‘(‘ and ‘)’. You can swap two consecutive characters in S1. Your task is to do it in as small a number of swapping operations as possible to obtain a string which contains S2 as a substring (you can assume that for the given input, this can always be done).

Input

The first line of the input file contains an integer t representing the number of test cases (t < 20). Then t test cases follow. Each test case has the following form:

• The first line contains S1
• The second line contains S2

Output

For each test case, output 0 iff you do not want to solve this test case. Otherwise, output a line containing the number 1 and two more lines of the following form:

• The first line contains an integer k representing the number of swap operations
• The second line contains k integers p1 p2,..., pk separated by single spaces, pi means that in the i-th operation, you swapped the i-th character and the (i+1)-th character in S1.

Score

Your task is to minimise your score for this problem. If you choose to solve a test case and the number of swap of operations is smaller than 5000, your score is equal to the number of operations. Otherwise, your score is 5000. Your total score is equal to the sum of scores for individual tests.

Example

Input:
1
ABCDEFGH
FC

Output:
1
3
5 4 3

Score:
3