#include <cassert>
#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;

const int MAXN = 100000 + 15;
const int MAXA = 500 + 15;

string s, t, w[MAXA], s1;
int f[MAXN * 4], tn, jump[MAXA][MAXN], ans[MAXN];

int main(int argc, const char * argv[]) {
	cin >> tn;
	while (tn--) {
		cin >> s >> t;
		s += "*";
		string current_part = "";
		int wn = 0;
		for(int i = 0; i < s.length(); i++)
			if (s[i] != '*')
				current_part += s[i];
			else if (current_part != "") {
				w[++wn] = current_part;
				current_part = "";
			}
		for(int i = 1; i <= wn; i++) {
			s1 = "_" + w[i] + "_" + t;
			f[1] = 0;
			for(int j = 2; j < s1.length(); j++) {
				int k = f[j - 1];
				while (k > 0 && s1[j] != s1[k + 1])
					k = f[k];
				if (s1[j] != s1[k + 1])
					f[j] = 0;
				else
					f[j] = k + 1;
			}
			jump[i][t.length() + 10] = (int)t.length() + 10;
			jump[i][t.length()] = (int)t.length() + 10;
			for(int j = 0; j < w[i].length(); j++)
				jump[i][t.length() - j] = (int)t.length() + 10;

			int cur_pos = (int)t.length() - (int)w[i].length();

			for(int j = (int)s1.length() - 1; (j >= w[i].length() + 2) && (cur_pos >= 0); j--, cur_pos--) {
				if (f[j] != (int)w[i].length())
					jump[i][cur_pos] = jump[i][cur_pos + 1];
				else
					jump[i][cur_pos] = cur_pos + (int)w[i].length();
			}
		}
		for(int i = 0; i < t.length(); i++) {
			int ps = i;
			for(int j = 1; j <= wn; j++)
				ps = jump[j][ps];
			if (ps == t.length() + 10)
				ans[i] = -1;
			else
				ans[i] = ps;
			if (wn == 0)
				ans[i] = i + 1;
		}
		for(int i = 0; i < t.length() - 1; i++)
			cout << ans[i] << " ";
		cout << ans[t.length() - 1] << endl;
	}
	return 0;
}