String Matching Example

Problem Description

You are given two strings $a$ and $b$, consisting only of lowercase letters. Count how many times $b$ occurs as a substring in $a$.

There are multiple test cases. The first line is the number of test cases $T$. Each test case consists of two lines: the first line is string $a$, the second line is string $b$.

For each test case output two lines: the first line is the number of occurrences, and the second line lists the starting index (1-based, where the first character of $a$ has index 1) of each occurrence. If $b$ does not occur, output two lines each containing $-1$.

Input Format

The first line contains an integer $T$.

The following $2T$ lines each contain one string.

Output Format

Output $2T$ lines, each containing several integers. See the description above.

Sample Input

3
abababa
aba
aaaaaa
bb
abcabcab
abcab

Sample Output

3
1 3 5
-1
-1
2
1 4

Constraints

For all data: $1 \leq T \leq 10$, $1 \leq |a|, |b| \leq 10^5$, and both strings consist only of lowercase letters.