/* 
   Copyright 2012 Jakub "Cubix651" Cisło
   Searching pattern in text - KMP algorithm. Complexity: O(n+m)
*/
#include <cstdio>
#include <cstring>
const int MAX = 10000005;
 
int t, n, m, p[MAX], x, w;
char pat[MAX], txt[MAX];
 
int main()
{
	scanf("%d", &t);
	while(t--)
	{
		scanf("%d", &n);
		scanf("%s", pat);
		scanf("%s", txt);
		m = strlen(txt);
 
		//calculating prefix array of patern
		p[0] = -1;
		p[1] = x = w = 0;
		for(int i = 1; i < n; ++i)
		{
			x = p[i];
			while(x != -1 && pat[i] != pat[x])
				x = p[x];
			p[i+1] = x+1;
		}
 
		//searching pattern in text with prefix array
		for(int i = 0; i < m; ++i)
		{
			x = w;
			while(x != -1 && txt[i] != pat[x])
				x = p[x];
			w = x+1;
			if(w == n)
				printf("%d\n", i-n+1);
		}
	}
	return 0;
}

LyogCiAgIENvcHlyaWdodCAyMDEyIEpha3ViICJDdWJpeDY1MSIgQ2lzxYJvCiAgIFNlYXJjaGluZyBwYXR0ZXJuIGluIHRleHQgLSBLTVAgYWxnb3JpdGhtLiBDb21wbGV4aXR5OiBPKG4rbSkKKi8KI2luY2x1ZGUgPGNzdGRpbz4KI2luY2x1ZGUgPGNzdHJpbmc+CmNvbnN0IGludCBNQVggPSAxMDAwMDAwNTsKCmludCB0LCBuLCBtLCBwW01BWF0sIHgsIHc7CmNoYXIgcGF0W01BWF0sIHR4dFtNQVhdOwoKaW50IG1haW4oKQp7CglzY2FuZigiJWQiLCAmdCk7Cgl3aGlsZSh0LS0pCgl7CgkJc2NhbmYoIiVkIiwgJm4pOwoJCXNjYW5mKCIlcyIsIHBhdCk7CgkJc2NhbmYoIiVzIiwgdHh0KTsKCQltID0gc3RybGVuKHR4dCk7CgkJCgkJLy9jYWxjdWxhdGluZyBwcmVmaXggYXJyYXkgb2YgcGF0ZXJuCgkJcFswXSA9IC0xOwoJCXBbMV0gPSB4ID0gdyA9IDA7CgkJZm9yKGludCBpID0gMTsgaSA8IG47ICsraSkKCQl7CgkJCXggPSBwW2ldOwoJCQl3aGlsZSh4ICE9IC0xICYmIHBhdFtpXSAhPSBwYXRbeF0pCgkJCQl4ID0gcFt4XTsKCQkJcFtpKzFdID0geCsxOwoJCX0KCQkKCQkvL3NlYXJjaGluZyBwYXR0ZXJuIGluIHRleHQgd2l0aCBwcmVmaXggYXJyYXkKCQlmb3IoaW50IGkgPSAwOyBpIDwgbTsgKytpKQoJCXsKCQkJeCA9IHc7CgkJCXdoaWxlKHggIT0gLTEgJiYgdHh0W2ldICE9IHBhdFt4XSkKCQkJCXggPSBwW3hdOwoJCQl3ID0geCsxOwoJCQlpZih3ID09IG4pCgkJCQlwcmludGYoIiVkXG4iLCBpLW4rMSk7CgkJfQoJfQoJcmV0dXJuIDA7Cn0=

MwoyCm5hCmJhbmFuYW5vYmFubwo2CmZvb2Jhcgpmb28KOQpmb29iYXJmb28KYmFyZm9vYmFyZm9vYmFyZm9vYmFyZm9vYmFyZm9v

3
2
na
banananobano
6
foobar
foo
9
foobarfoo
barfoobarfoobarfoobarfoobarfoo