Oh!! Mankind is in trouble again. This time, it's a deadly disease spreading at a rate never seen before. The need of the hour is to set up efficient virus detectors. You are the lead at Central Hospital and you need to find a fast and reliable way to detect the footprints of the virus DNA in that of the patient.

The DNA of the patient as well as of the virus consists of lowercase letters. Since the collected data is raw, there may be some errors. You will need to find all substrings in the patient DNA that either exactly match the virus DNA or have at most one mismatch, i.e., a difference in at most one location. 

For example, "aa" and "aa" are matching, "ab" and "aa" are matching, while "abb" and "bab" are not.

Function Description

Complete the virusIndices function in the editor below.  It should print a list of space-separated integers that represent the starting indices of matching substrings in increasing order, or No match!.

virusIndices has the following parameter(s):  

p: a string that represents patient DNA  
v: a string that represents virus DNA  

Input Format

The first line contains an integer $t$, the number of test cases. 

 . 
Each of the next $t$ lines contains two space-separated strings $p$ (the patient DNA) and $v}$ (the virus DNA).  

Constraints

$1\leq t\leq10$
$1\leq|p|,|v|\leq10^5$  
All characters in $p$ and $v\in a s c i i[a-z]$.

Output Format

For each test case, output a single line containing a space-delimited list of starting indices ($0$-indexed) of substrings of $p$ which are matching with $v$ according to the condition mentioned above. The indices have to be in increasing order. If there is no matching substring, output No Match!.  

Sample Input 0
3
abbab ba
hello world
banana nan

Sample Output 0
1 2
No Match!
0 2

Explanation 0

For the first case, the substrings of $p$ starting at indices $1$ and $2$ are "bb" and "ba" and they are matching with the string $v$ which is "ba". 

For the second case, there are no matching substrings so the output is No Match!. 

For the third case, the substrings of $p$ starting at indices $0$ and $2$ are "ban" and "nan" and they are matching with the string $v$ which is "nan".  

Sample Input 1
3
cgatcg gc
atcgatcga cgg
aardvark ab

Sample Output 1
1 3
2 6
0 1 5

Explanation 1

For the first case, the substrings of $p$ starting at indices $1$ and $3$ are "ga" and "gc" and they are matching with the string $v$ which is "gc". 

For the second case, the substrings of $p$ starting at indices $2$ and $6$ are "cga" and "cga" and they are matching with the string $v$ which is "cgg". 

For the third case, the substrings of $p$ starting at indices $0$, $1$ and $5$ are "aa", "ar" and "ar" and they are matching with the string $v$ which is "ab".

Difficulty: HARD
Tags: String algorithms

Starter code:

Solutions:
from collections import defaultdict
import re
_DEBUG = 0

def WM_approx_Ham1_search(pattern, text):
	m = len(pattern)
	S_table = defaultdict(int)
	for (i, c) in enumerate(pattern):
		S_table[c] |= 1 << i
	R0 = 0
	R1 = 0
	mask = 1 << m - 1
	for (j, c) in enumerate(text):
		S = S_table[c]
		shR0 = R0 << 1 | 1
		R0 = shR0 & S
		R1 = (R1 << 1 | 1) & S | shR0
		if _DEBUG:
			print('j= %2d msk=%s S=%s R0=%s R1=%s' % tuple([j] + map(bitstr, [mask, S, R0, R1])))
		if R0 & mask:
			yield (0, j - m + 1)
		elif R1 & mask:
			yield (1, j - m + 1)
if _DEBUG:

	def bitstr(num, mlen=8):
		wstr = ''
		for i in xrange(mlen):
			if num & 1:
				wstr = '1' + wstr
			else:
				wstr = '0' + wstr
			num >>= 1
		return wstr

def Ham_dist(s1, s2):
	assert len(s1) == len(s2)
	return sum((c1 != c2 for (c1, c2) in zip(s1, s2)))

def long_check(pattern, text):
	m = len(pattern)
	for i in xrange(len(text) - m + 1):
		d = Ham_dist(pattern, text[i:i + m])
		if d < 2:
			yield (d, i)

def Paul_McGuire_regex(pattern, text):
	searchSeqREStr = '(' + pattern + ')|(' + ')|('.join((pattern[:i] + '[a-z]'.replace(c, '') + pattern[i + 1:] for (i, c) in enumerate(pattern))) + ')'
	searchSeqRE = re.compile(searchSeqREStr)
	for match in searchSeqRE.finditer(text):
		locn = match.start()
		dist = int(bool(match.lastindex - 1))
		yield (dist, locn)
t = int(input())
for i in range(t):
	(p, v) = input().split()
	r = []
	for l in list(WM_approx_Ham1_search(v, p)):
		r.append(l[1])
	print(' '.join(map(str, r)) if r else 'No Match!')


from collections import defaultdict
import re
_DEBUG = 0

def WM_approx_Ham1_search(pattern, text):
	m = len(pattern)
	S_table = defaultdict(int)
	for (i, c) in enumerate(pattern):
		S_table[c] |= 1 << i
	R0 = 0
	R1 = 0
	mask = 1 << m - 1
	for (j, c) in enumerate(text):
		S = S_table[c]
		shR0 = R0 << 1 | 1
		R0 = shR0 & S
		R1 = (R1 << 1 | 1) & S | shR0
		if _DEBUG:
			print('j= %2d msk=%s S=%s R0=%s R1=%s' % tuple([j] + map(bitstr, [mask, S, R0, R1])))
		if R0 & mask:
			yield (0, j - m + 1)
		elif R1 & mask:
			yield (1, j - m + 1)
if _DEBUG:

	def bitstr(num, mlen=8):
		wstr = ''
		for i in xrange(mlen):
			if num & 1:
				wstr = '1' + wstr
			else:
				wstr = '0' + wstr
			num >>= 1
		return wstr

def Ham_dist(s1, s2):
	assert len(s1) == len(s2)
	return sum((c1 != c2 for (c1, c2) in zip(s1, s2)))

def long_check(pattern, text):
	m = len(pattern)
	for i in xrange(len(text) - m + 1):
		d = Ham_dist(pattern, text[i:i + m])
		if d < 2:
			yield (d, i)

def Paul_McGuire_regex(pattern, text):
	searchSeqREStr = '(' + pattern + ')|(' + ')|('.join((pattern[:i] + '[a-z]'.replace(c, '') + pattern[i + 1:] for (i, c) in enumerate(pattern))) + ')'
	searchSeqRE = re.compile(searchSeqREStr)
	for match in searchSeqRE.finditer(text):
		locn = match.start()
		dist = int(bool(match.lastindex - 1))
		yield (dist, locn)
t = int(input())
for i in range(t):
	(p, v) = input().split()
	r = []
	for l in list(WM_approx_Ham1_search(v, p)):
		r.append(l[1])
	print(' '.join(map(str, r)) if r else 'No Match!')


class saveHuman:

	def printCheckDNA(self, dna, virus):
		lenVirus = len(virus)
		lenDna = len(dna)
		listVirusDna = []
		if lenVirus == 1:
			return ' '.join([str(i) for i in range(lenDna)])
		for i in range(lenDna - lenVirus + 1):
			subDna = dna[i:i + lenVirus]
			if subDna == virus or self.checkDNA(subDna, virus, lenVirus):
				listVirusDna.append(str(i))
		return ' '.join(listVirusDna) if len(listVirusDna) > 0 else 'No Match!'

	def checkDNA(self, dna, virus, lenVirus):
		if lenVirus == 1:
			return True
		subLen = int((lenVirus + 1) / 2)
		if dna[:subLen] == virus[:subLen]:
			return self.checkDNA(dna[subLen:], virus[subLen:], lenVirus - subLen)
		elif dna[subLen:] == virus[subLen:]:
			return self.checkDNA(dna[:subLen], virus[:subLen], subLen)
		else:
			return False
task = saveHuman()
for _ in range(int(input())):
	(dna, virus) = input().split()
	print(task.printCheckDNA(dna, virus))


import os
import sys

def search_without_sentinel(pattern, text):
	s = pattern + text
	Z = [0] * len(s)
	Z[0] = len(s)
	rt = 0
	lt = 0
	occurrence = []
	for k in range(1, len(s)):
		if k > rt:
			n = 0
			while n + k < len(s) and s[n] == s[n + k]:
				n += 1
			Z[k] = n
			if n > 0:
				lt = k
				rt = k + n - 1
		else:
			p = k - lt
			right_part_len = rt - k + 1
			if Z[p] < right_part_len:
				Z[k] = Z[p]
			else:
				i = rt + 1
				while i < len(s) and s[i] == s[i - k]:
					i += 1
				Z[k] = i - k
				lt = k
				rt = i - 1
		Z[k] = min(len(pattern), Z[k])
	return Z[len(pattern):]

def virusIndices(p, v):
	Z_forwards = search_without_sentinel(v, p)
	Z_backwards = search_without_sentinel(v[::-1], p[::-1])
	Z_backwards.reverse()
	indexes = []
	for i in range(len(p) - len(v) + 1):
		if Z_forwards[i] + Z_backwards[i + len(v) - 1] >= len(v) - 1:
			indexes.append(str(i))
	if len(indexes) == 0:
		print('No Match!')
	else:
		print(' '.join(indexes))
t = int(input())
for t_itr in range(t):
	pv = input().split()
	p = pv[0]
	v = pv[1]
	virusIndices(p, v)


import os
import sys
import math
import re
from collections import defaultdict

def virusIndices(p, v):

	def WM_approx_Ham1_search(pattern, text):
		m = len(pattern)
		S_table = defaultdict(int)
		for (i, c) in enumerate(pattern):
			S_table[c] |= 1 << i
		R0 = 0
		R1 = 0
		mask = 1 << m - 1
		for (j, c) in enumerate(text):
			S = S_table[c]
			shR0 = R0 << 1 | 1
			R0 = shR0 & S
			R1 = (R1 << 1 | 1) & S | shR0
			if R0 & mask:
				yield (j - m + 1)
			elif R1 & mask:
				yield (j - m + 1)
	matches = list(WM_approx_Ham1_search(v, p))
	if not len(matches):
		print('No Match!')
	else:
		print(' '.join((str(ind) for ind in matches)))
t = int(input())
for t_itr in range(t):
	pv = input().split()
	p = pv[0]
	v = pv[1]
	virusIndices(p, v)


class saveHuman:

	def printCheckDNA(self, dna, virus):
		lenVirus = len(virus)
		lenDna = len(dna)
		listVirusDna = []
		if lenVirus == 1:
			return ' '.join([str(i) for i in range(lenDna)])
		for i in range(lenDna - lenVirus + 1):
			subDna = dna[i:i + lenVirus]
			if subDna == virus or self.checkDNA(subDna, virus, lenVirus):
				listVirusDna.append(str(i))
		return ' '.join(listVirusDna) if len(listVirusDna) > 0 else 'No Match!'

	def checkDNA(self, dna, virus, lenVirus):
		if lenVirus == 1:
			return True
		subLen = int((lenVirus + 1) / 2)
		if dna[:subLen] == virus[:subLen]:
			return self.checkDNA(dna[subLen:], virus[subLen:], lenVirus - subLen)
		elif dna[subLen:] == virus[subLen:]:
			return self.checkDNA(dna[:subLen], virus[:subLen], subLen)
		else:
			return False
task = saveHuman()
for _ in range(int(input())):
	(dna, virus) = input().split()
	print(task.printCheckDNA(dna, virus))


from collections import defaultdict
import re
_DEBUG = 0

def WM_approx_Ham1_search(pattern, text):
	m = len(pattern)
	S_table = defaultdict(int)
	for (i, c) in enumerate(pattern):
		S_table[c] |= 1 << i
	R0 = 0
	R1 = 0
	mask = 1 << m - 1
	for (j, c) in enumerate(text):
		S = S_table[c]
		shR0 = R0 << 1 | 1
		R0 = shR0 & S
		R1 = (R1 << 1 | 1) & S | shR0
		if _DEBUG:
			print('j= %2d msk=%s S=%s R0=%s R1=%s' % tuple([j] + map(bitstr, [mask, S, R0, R1])))
		if R0 & mask:
			yield (0, j - m + 1)
		elif R1 & mask:
			yield (1, j - m + 1)
if _DEBUG:

	def bitstr(num, mlen=8):
		wstr = ''
		for i in xrange(mlen):
			if num & 1:
				wstr = '1' + wstr
			else:
				wstr = '0' + wstr
			num >>= 1
		return wstr

def Ham_dist(s1, s2):
	assert len(s1) == len(s2)
	return sum((c1 != c2 for (c1, c2) in zip(s1, s2)))

def long_check(pattern, text):
	m = len(pattern)
	for i in xrange(len(text) - m + 1):
		d = Ham_dist(pattern, text[i:i + m])
		if d < 2:
			yield (d, i)

def Paul_McGuire_regex(pattern, text):
	searchSeqREStr = '(' + pattern + ')|(' + ')|('.join((pattern[:i] + '[a-z]'.replace(c, '') + pattern[i + 1:] for (i, c) in enumerate(pattern))) + ')'
	searchSeqRE = re.compile(searchSeqREStr)
	for match in searchSeqRE.finditer(text):
		locn = match.start()
		dist = int(bool(match.lastindex - 1))
		yield (dist, locn)
t = int(input())
for i in range(t):
	(p, v) = input().split()
	r = []
	for l in list(WM_approx_Ham1_search(v, p)):
		r.append(l[1])
	print(' '.join(map(str, r)) if r else 'No Match!')


from collections import defaultdict
import re
_DEBUG = 0

def WM_approx_Ham1_search(pattern, text):
	m = len(pattern)
	S_table = defaultdict(int)
	for (i, c) in enumerate(pattern):
		S_table[c] |= 1 << i
	R0 = 0
	R1 = 0
	mask = 1 << m - 1
	for (j, c) in enumerate(text):
		S = S_table[c]
		shR0 = R0 << 1 | 1
		R0 = shR0 & S
		R1 = (R1 << 1 | 1) & S | shR0
		if _DEBUG:
			print('j= %2d msk=%s S=%s R0=%s R1=%s' % tuple([j] + map(bitstr, [mask, S, R0, R1])))
		if R0 & mask:
			yield (0, j - m + 1)
		elif R1 & mask:
			yield (1, j - m + 1)
if _DEBUG:

	def bitstr(num, mlen=8):
		wstr = ''
		for i in xrange(mlen):
			if num & 1:
				wstr = '1' + wstr
			else:
				wstr = '0' + wstr
			num >>= 1
		return wstr

def Ham_dist(s1, s2):
	assert len(s1) == len(s2)
	return sum((c1 != c2 for (c1, c2) in zip(s1, s2)))

def long_check(pattern, text):
	m = len(pattern)
	for i in xrange(len(text) - m + 1):
		d = Ham_dist(pattern, text[i:i + m])
		if d < 2:
			yield (d, i)

def Paul_McGuire_regex(pattern, text):
	searchSeqREStr = '(' + pattern + ')|(' + ')|('.join((pattern[:i] + '[a-z]'.replace(c, '') + pattern[i + 1:] for (i, c) in enumerate(pattern))) + ')'
	searchSeqRE = re.compile(searchSeqREStr)
	for match in searchSeqRE.finditer(text):
		locn = match.start()
		dist = int(bool(match.lastindex - 1))
		yield (dist, locn)
t = int(input())
for i in range(t):
	(p, v) = input().split()
	r = []
	for l in list(WM_approx_Ham1_search(v, p)):
		r.append(l[1])
	print(' '.join(map(str, r)) if r else 'No Match!')


from collections import defaultdict
import re
_DEBUG = 0

def WM_approx_Ham1_search(pattern, text):
	m = len(pattern)
	S_table = defaultdict(int)
	for (i, c) in enumerate(pattern):
		S_table[c] |= 1 << i
	R0 = 0
	R1 = 0
	mask = 1 << m - 1
	for (j, c) in enumerate(text):
		S = S_table[c]
		shR0 = R0 << 1 | 1
		R0 = shR0 & S
		R1 = (R1 << 1 | 1) & S | shR0
		if _DEBUG:
			print('j= %2d msk=%s S=%s R0=%s R1=%s' % tuple([j] + map(bitstr, [mask, S, R0, R1])))
		if R0 & mask:
			yield (0, j - m + 1)
		elif R1 & mask:
			yield (1, j - m + 1)
if _DEBUG:

	def bitstr(num, mlen=8):
		wstr = ''
		for i in xrange(mlen):
			if num & 1:
				wstr = '1' + wstr
			else:
				wstr = '0' + wstr
			num >>= 1
		return wstr

def Ham_dist(s1, s2):
	assert len(s1) == len(s2)
	return sum((c1 != c2 for (c1, c2) in zip(s1, s2)))

def long_check(pattern, text):
	m = len(pattern)
	for i in xrange(len(text) - m + 1):
		d = Ham_dist(pattern, text[i:i + m])
		if d < 2:
			yield (d, i)

def Paul_McGuire_regex(pattern, text):
	searchSeqREStr = '(' + pattern + ')|(' + ')|('.join((pattern[:i] + '[a-z]'.replace(c, '') + pattern[i + 1:] for (i, c) in enumerate(pattern))) + ')'
	searchSeqRE = re.compile(searchSeqREStr)
	for match in searchSeqRE.finditer(text):
		locn = match.start()
		dist = int(bool(match.lastindex - 1))
		yield (dist, locn)
t = int(input())
for i in range(t):
	(p, v) = input().split()
	r = []
	for l in list(WM_approx_Ham1_search(v, p)):
		r.append(l[1])
	print(' '.join(map(str, r)) if r else 'No Match!')


from collections import defaultdict
import re
_DEBUG = 0

def WM_approx_Ham1_search(pattern, text):
	m = len(pattern)
	S_table = defaultdict(int)
	for (i, c) in enumerate(pattern):
		S_table[c] |= 1 << i
	R0 = 0
	R1 = 0
	mask = 1 << m - 1
	for (j, c) in enumerate(text):
		S = S_table[c]
		shR0 = R0 << 1 | 1
		R0 = shR0 & S
		R1 = (R1 << 1 | 1) & S | shR0
		if _DEBUG:
			print('j= %2d msk=%s S=%s R0=%s R1=%s' % tuple([j] + map(bitstr, [mask, S, R0, R1])))
		if R0 & mask:
			yield (0, j - m + 1)
		elif R1 & mask:
			yield (1, j - m + 1)
if _DEBUG:

	def bitstr(num, mlen=8):
		wstr = ''
		for i in xrange(mlen):
			if num & 1:
				wstr = '1' + wstr
			else:
				wstr = '0' + wstr
			num >>= 1
		return wstr

def Ham_dist(s1, s2):
	assert len(s1) == len(s2)
	return sum((c1 != c2 for (c1, c2) in zip(s1, s2)))

def long_check(pattern, text):
	m = len(pattern)
	for i in xrange(len(text) - m + 1):
		d = Ham_dist(pattern, text[i:i + m])
		if d < 2:
			yield (d, i)

def Paul_McGuire_regex(pattern, text):
	searchSeqREStr = '(' + pattern + ')|(' + ')|('.join((pattern[:i] + '[a-z]'.replace(c, '') + pattern[i + 1:] for (i, c) in enumerate(pattern))) + ')'
	searchSeqRE = re.compile(searchSeqREStr)
	for match in searchSeqRE.finditer(text):
		locn = match.start()
		dist = int(bool(match.lastindex - 1))
		yield (dist, locn)
t = int(input())
for i in range(t):
	(p, v) = input().split()
	r = []
	for l in list(WM_approx_Ham1_search(v, p)):
		r.append(l[1])
	print(' '.join(map(str, r)) if r else 'No Match!')


from collections import defaultdict
import re
_DEBUG = 0

def WM_approx_Ham1_search(pattern, text):
	m = len(pattern)
	S_table = defaultdict(int)
	for (i, c) in enumerate(pattern):
		S_table[c] |= 1 << i
	R0 = 0
	R1 = 0
	mask = 1 << m - 1
	for (j, c) in enumerate(text):
		S = S_table[c]
		shR0 = R0 << 1 | 1
		R0 = shR0 & S
		R1 = (R1 << 1 | 1) & S | shR0
		if _DEBUG:
			print('j= %2d msk=%s S=%s R0=%s R1=%s' % tuple([j] + map(bitstr, [mask, S, R0, R1])))
		if R0 & mask:
			yield (0, j - m + 1)
		elif R1 & mask:
			yield (1, j - m + 1)
if _DEBUG:

	def bitstr(num, mlen=8):
		wstr = ''
		for i in xrange(mlen):
			if num & 1:
				wstr = '1' + wstr
			else:
				wstr = '0' + wstr
			num >>= 1
		return wstr

def Ham_dist(s1, s2):
	assert len(s1) == len(s2)
	return sum((c1 != c2 for (c1, c2) in zip(s1, s2)))

def long_check(pattern, text):
	m = len(pattern)
	for i in xrange(len(text) - m + 1):
		d = Ham_dist(pattern, text[i:i + m])
		if d < 2:
			yield (d, i)

def Paul_McGuire_regex(pattern, text):
	searchSeqREStr = '(' + pattern + ')|(' + ')|('.join((pattern[:i] + '[a-z]'.replace(c, '') + pattern[i + 1:] for (i, c) in enumerate(pattern))) + ')'
	searchSeqRE = re.compile(searchSeqREStr)
	for match in searchSeqRE.finditer(text):
		locn = match.start()
		dist = int(bool(match.lastindex - 1))
		yield (dist, locn)
t = int(input())
for i in range(t):
	(p, v) = input().split()
	r = []
	for l in list(WM_approx_Ham1_search(v, p)):
		r.append(l[1])
	print(' '.join(map(str, r)) if r else 'No Match!')


from collections import defaultdict
import re
_DEBUG = 0

def WM_approx_Ham1_search(pattern, text):
	m = len(pattern)
	S_table = defaultdict(int)
	for (i, c) in enumerate(pattern):
		S_table[c] |= 1 << i
	R0 = 0
	R1 = 0
	mask = 1 << m - 1
	for (j, c) in enumerate(text):
		S = S_table[c]
		shR0 = R0 << 1 | 1
		R0 = shR0 & S
		R1 = (R1 << 1 | 1) & S | shR0
		if _DEBUG:
			print('j= %2d msk=%s S=%s R0=%s R1=%s' % tuple([j] + map(bitstr, [mask, S, R0, R1])))
		if R0 & mask:
			yield (0, j - m + 1)
		elif R1 & mask:
			yield (1, j - m + 1)
if _DEBUG:

	def bitstr(num, mlen=8):
		wstr = ''
		for i in xrange(mlen):
			if num & 1:
				wstr = '1' + wstr
			else:
				wstr = '0' + wstr
			num >>= 1
		return wstr

def Ham_dist(s1, s2):
	assert len(s1) == len(s2)
	return sum((c1 != c2 for (c1, c2) in zip(s1, s2)))

def long_check(pattern, text):
	m = len(pattern)
	for i in xrange(len(text) - m + 1):
		d = Ham_dist(pattern, text[i:i + m])
		if d < 2:
			yield (d, i)

def Paul_McGuire_regex(pattern, text):
	searchSeqREStr = '(' + pattern + ')|(' + ')|('.join((pattern[:i] + '[a-z]'.replace(c, '') + pattern[i + 1:] for (i, c) in enumerate(pattern))) + ')'
	searchSeqRE = re.compile(searchSeqREStr)
	for match in searchSeqRE.finditer(text):
		locn = match.start()
		dist = int(bool(match.lastindex - 1))
		yield (dist, locn)
t = int(input())
for i in range(t):
	(p, v) = input().split()
	r = []
	for l in list(WM_approx_Ham1_search(v, p)):
		r.append(l[1])
	print(' '.join(map(str, r)) if r else 'No Match!')


from collections import defaultdict
import re
_DEBUG = 0

def WM_approx_Ham1_search(pattern, text):
	m = len(pattern)
	S_table = defaultdict(int)
	for (i, c) in enumerate(pattern):
		S_table[c] |= 1 << i
	R0 = 0
	R1 = 0
	mask = 1 << m - 1
	for (j, c) in enumerate(text):
		S = S_table[c]
		shR0 = R0 << 1 | 1
		R0 = shR0 & S
		R1 = (R1 << 1 | 1) & S | shR0
		if _DEBUG:
			print('j= %2d msk=%s S=%s R0=%s R1=%s' % tuple([j] + map(bitstr, [mask, S, R0, R1])))
		if R0 & mask:
			yield (0, j - m + 1)
		elif R1 & mask:
			yield (1, j - m + 1)
if _DEBUG:

	def bitstr(num, mlen=8):
		wstr = ''
		for i in xrange(mlen):
			if num & 1:
				wstr = '1' + wstr
			else:
				wstr = '0' + wstr
			num >>= 1
		return wstr

def Ham_dist(s1, s2):
	assert len(s1) == len(s2)
	return sum((c1 != c2 for (c1, c2) in zip(s1, s2)))

def long_check(pattern, text):
	m = len(pattern)
	for i in xrange(len(text) - m + 1):
		d = Ham_dist(pattern, text[i:i + m])
		if d < 2:
			yield (d, i)

def Paul_McGuire_regex(pattern, text):
	searchSeqREStr = '(' + pattern + ')|(' + ')|('.join((pattern[:i] + '[a-z]'.replace(c, '') + pattern[i + 1:] for (i, c) in enumerate(pattern))) + ')'
	searchSeqRE = re.compile(searchSeqREStr)
	for match in searchSeqRE.finditer(text):
		locn = match.start()
		dist = int(bool(match.lastindex - 1))
		yield (dist, locn)
t = int(input())
for i in range(t):
	(p, v) = input().split()
	r = []
	for l in list(WM_approx_Ham1_search(v, p)):
		r.append(l[1])
	print(' '.join(map(str, r)) if r else 'No Match!')


import os
import sys

def search_without_sentinel(pattern, text):
	s = pattern + text
	Z = [0] * len(s)
	Z[0] = len(s)
	rt = 0
	lt = 0
	occurrence = []
	for k in range(1, len(s)):
		if k > rt:
			n = 0
			while n + k < len(s) and s[n] == s[n + k]:
				n += 1
			Z[k] = n
			if n > 0:
				lt = k
				rt = k + n - 1
		else:
			p = k - lt
			right_part_len = rt - k + 1
			if Z[p] < right_part_len:
				Z[k] = Z[p]
			else:
				i = rt + 1
				while i < len(s) and s[i] == s[i - k]:
					i += 1
				Z[k] = i - k
				lt = k
				rt = i - 1
		Z[k] = min(len(pattern), Z[k])
	return Z[len(pattern):]

def virusIndices(p, v):
	Z_forwards = search_without_sentinel(v, p)
	Z_backwards = search_without_sentinel(v[::-1], p[::-1])
	Z_backwards.reverse()
	indexes = []
	for i in range(len(p) - len(v) + 1):
		if Z_forwards[i] + Z_backwards[i + len(v) - 1] >= len(v) - 1:
			indexes.append(str(i))
	if len(indexes) == 0:
		print('No Match!')
	else:
		print(' '.join(indexes))
t = int(input())
for t_itr in range(t):
	pv = input().split()
	p = pv[0]
	v = pv[1]
	virusIndices(p, v)


from collections import defaultdict
import re
_DEBUG = 0

def WM_approx_Ham1_search(pattern, text):
	m = len(pattern)
	S_table = defaultdict(int)
	for (i, c) in enumerate(pattern):
		S_table[c] |= 1 << i
	R0 = 0
	R1 = 0
	mask = 1 << m - 1
	for (j, c) in enumerate(text):
		S = S_table[c]
		shR0 = R0 << 1 | 1
		R0 = shR0 & S
		R1 = (R1 << 1 | 1) & S | shR0
		if _DEBUG:
			print('j= %2d msk=%s S=%s R0=%s R1=%s' % tuple([j] + map(bitstr, [mask, S, R0, R1])))
		if R0 & mask:
			yield (0, j - m + 1)
		elif R1 & mask:
			yield (1, j - m + 1)
if _DEBUG:

	def bitstr(num, mlen=8):
		wstr = ''
		for i in xrange(mlen):
			if num & 1:
				wstr = '1' + wstr
			else:
				wstr = '0' + wstr
			num >>= 1
		return wstr

def Ham_dist(s1, s2):
	assert len(s1) == len(s2)
	return sum((c1 != c2 for (c1, c2) in zip(s1, s2)))

def long_check(pattern, text):
	m = len(pattern)
	for i in xrange(len(text) - m + 1):
		d = Ham_dist(pattern, text[i:i + m])
		if d < 2:
			yield (d, i)

def Paul_McGuire_regex(pattern, text):
	searchSeqREStr = '(' + pattern + ')|(' + ')|('.join((pattern[:i] + '[a-z]'.replace(c, '') + pattern[i + 1:] for (i, c) in enumerate(pattern))) + ')'
	searchSeqRE = re.compile(searchSeqREStr)
	for match in searchSeqRE.finditer(text):
		locn = match.start()
		dist = int(bool(match.lastindex - 1))
		yield (dist, locn)
t = int(input())
for i in range(t):
	(p, v) = input().split()
	r = []
	for l in list(WM_approx_Ham1_search(v, p)):
		r.append(l[1])
	print(' '.join(map(str, r)) if r else 'No Match!')


class saveHuman:

	def printCheckDNA(self, dna, virus):
		lenVirus = len(virus)
		lenDna = len(dna)
		listVirusDna = []
		if lenVirus == 1:
			return ' '.join([str(i) for i in range(lenDna)])
		for i in range(lenDna - lenVirus + 1):
			subDna = dna[i:i + lenVirus]
			if subDna == virus or self.checkDNA(subDna, virus, lenVirus):
				listVirusDna.append(str(i))
		return ' '.join(listVirusDna) if len(listVirusDna) > 0 else 'No Match!'

	def checkDNA(self, dna, virus, lenVirus):
		if lenVirus == 1:
			return True
		subLen = int((lenVirus + 1) / 2)
		if dna[:subLen] == virus[:subLen]:
			return self.checkDNA(dna[subLen:], virus[subLen:], lenVirus - subLen)
		elif dna[subLen:] == virus[subLen:]:
			return self.checkDNA(dna[:subLen], virus[:subLen], subLen)
		else:
			return False
task = saveHuman()
for _ in range(int(input())):
	(dna, virus) = input().split()
	print(task.printCheckDNA(dna, virus))


import os
import sys
import math
import re
from collections import defaultdict

def virusIndices(p, v):

	def WM_approx_Ham1_search(pattern, text):
		m = len(pattern)
		S_table = defaultdict(int)
		for (i, c) in enumerate(pattern):
			S_table[c] |= 1 << i
		R0 = 0
		R1 = 0
		mask = 1 << m - 1
		for (j, c) in enumerate(text):
			S = S_table[c]
			shR0 = R0 << 1 | 1
			R0 = shR0 & S
			R1 = (R1 << 1 | 1) & S | shR0
			if R0 & mask:
				yield (j - m + 1)
			elif R1 & mask:
				yield (j - m + 1)
	matches = list(WM_approx_Ham1_search(v, p))
	if not len(matches):
		print('No Match!')
	else:
		print(' '.join((str(ind) for ind in matches)))
t = int(input())
for t_itr in range(t):
	pv = input().split()
	p = pv[0]
	v = pv[1]
	virusIndices(p, v)


import os
import sys
import re

def match_mini(w1, w2):
	s = 0
	for i in range(len(w1)):
		if w1[i] != w2[i]:
			s += 1
			if s > 1:
				return 0
	return 1

def match(w1, w2):
	length = len(w1)
	if length < 10:
		return match_mini(w1, w2)
	w11 = w1[:length // 2]
	w21 = w2[:length // 2]
	w12 = w1[length // 2:]
	w22 = w2[length // 2:]
	p1 = w11 == w21
	p2 = w12 == w22
	if p1 and p2:
		return 1
	elif p1 and (not p2):
		return match(w12, w22)
	elif p2 and (not p1):
		return match(w11, w21)
	else:
		return 0

def virusIndices(p, v):
	result = []
	p_len = len(p)
	v_len = len(v)
	for i in range(p_len - v_len + 1):
		seq = p[i:i + v_len]
		if match(seq, v):
			result.append(i)
	if len(result):
		print(*result)
	else:
		print('No Match!')
t = int(input())
for t_itr in range(t):
	pv = input().split()
	p = pv[0]
	v = pv[1]
	virusIndices(p, v)


from collections import defaultdict
import re
_DEBUG = 0

def WM_approx_Ham1_search(pattern, text):
	m = len(pattern)
	S_table = defaultdict(int)
	for (i, c) in enumerate(pattern):
		S_table[c] |= 1 << i
	R0 = 0
	R1 = 0
	mask = 1 << m - 1
	for (j, c) in enumerate(text):
		S = S_table[c]
		shR0 = R0 << 1 | 1
		R0 = shR0 & S
		R1 = (R1 << 1 | 1) & S | shR0
		if _DEBUG:
			print('j= %2d msk=%s S=%s R0=%s R1=%s' % tuple([j] + map(bitstr, [mask, S, R0, R1])))
		if R0 & mask:
			yield (0, j - m + 1)
		elif R1 & mask:
			yield (1, j - m + 1)
if _DEBUG:

	def bitstr(num, mlen=8):
		wstr = ''
		for i in xrange(mlen):
			if num & 1:
				wstr = '1' + wstr
			else:
				wstr = '0' + wstr
			num >>= 1
		return wstr

def Ham_dist(s1, s2):
	assert len(s1) == len(s2)
	return sum((c1 != c2 for (c1, c2) in zip(s1, s2)))

def long_check(pattern, text):
	m = len(pattern)
	for i in xrange(len(text) - m + 1):
		d = Ham_dist(pattern, text[i:i + m])
		if d < 2:
			yield (d, i)

def Paul_McGuire_regex(pattern, text):
	searchSeqREStr = '(' + pattern + ')|(' + ')|('.join((pattern[:i] + '[a-z]'.replace(c, '') + pattern[i + 1:] for (i, c) in enumerate(pattern))) + ')'
	searchSeqRE = re.compile(searchSeqREStr)
	for match in searchSeqRE.finditer(text):
		locn = match.start()
		dist = int(bool(match.lastindex - 1))
		yield (dist, locn)
t = int(input())
for i in range(t):
	(p, v) = input().split()
	r = []
	for l in list(WM_approx_Ham1_search(v, p)):
		r.append(l[1])
	print(' '.join(map(str, r)) if r else 'No Match!')


import os
import sys

def virusIndices(p: str, v: str):
	if len(v) == 1:
		print(' '.join(map(str, range(len(p)))))
		return
	l = len(v)
	indecies = set()

	def uptoone(a, b, m=64):
		l = len(a)
		if l < m:
			errors = False
			for (c1, c2) in zip(a, b):
				if c1 != c2:
					if errors:
						return False
					errors = True
			return True
		l = l // 2
		if a.startswith(b[:l]):
			return uptoone(a[l:], b[l:])
		return a[l:].startswith(b[l:]) and uptoone(a[:l], b[:l])
	for i in range(len(p) - l + 1):
		if uptoone(p[i:i + l], v):
			indecies.add(i)
	if indecies:
		print(' '.join(map(str, sorted(indecies))))
	else:
		print('No Match!')
t = int(input())
for t_itr in range(t):
	pv = input().split()
	p = pv[0]
	v = pv[1]
	virusIndices(p, v)


class saveHuman:

	def printCheckDNA(self, dna, virus):
		lenVirus = len(virus)
		lenDna = len(dna)
		listVirusDna = []
		if lenVirus == 1:
			return ' '.join([str(i) for i in range(lenDna)])
		for i in range(lenDna - lenVirus + 1):
			subDna = dna[i:i + lenVirus]
			if subDna == virus or self.checkDNA(subDna, virus, lenVirus):
				listVirusDna.append(str(i))
		return ' '.join(listVirusDna) if len(listVirusDna) > 0 else 'No Match!'

	def checkDNA(self, dna, virus, lenVirus):
		if lenVirus == 1:
			return True
		subLen = int((lenVirus + 1) / 2)
		if dna[:subLen] == virus[:subLen]:
			return self.checkDNA(dna[subLen:], virus[subLen:], lenVirus - subLen)
		elif dna[subLen:] == virus[subLen:]:
			return self.checkDNA(dna[:subLen], virus[:subLen], subLen)
		else:
			return False
task = saveHuman()
for _ in range(int(input())):
	(dna, virus) = input().split()
	print(task.printCheckDNA(dna, virus))


from collections import defaultdict
import re
_DEBUG = 0

def WM_approx_Ham1_search(pattern, text):
	m = len(pattern)
	S_table = defaultdict(int)
	for (i, c) in enumerate(pattern):
		S_table[c] |= 1 << i
	R0 = 0
	R1 = 0
	mask = 1 << m - 1
	for (j, c) in enumerate(text):
		S = S_table[c]
		shR0 = R0 << 1 | 1
		R0 = shR0 & S
		R1 = (R1 << 1 | 1) & S | shR0
		if _DEBUG:
			print('j= %2d msk=%s S=%s R0=%s R1=%s' % tuple([j] + map(bitstr, [mask, S, R0, R1])))
		if R0 & mask:
			yield (0, j - m + 1)
		elif R1 & mask:
			yield (1, j - m + 1)
if _DEBUG:

	def bitstr(num, mlen=8):
		wstr = ''
		for i in xrange(mlen):
			if num & 1:
				wstr = '1' + wstr
			else:
				wstr = '0' + wstr
			num >>= 1
		return wstr

def Ham_dist(s1, s2):
	assert len(s1) == len(s2)
	return sum((c1 != c2 for (c1, c2) in zip(s1, s2)))

def long_check(pattern, text):
	m = len(pattern)
	for i in xrange(len(text) - m + 1):
		d = Ham_dist(pattern, text[i:i + m])
		if d < 2:
			yield (d, i)

def Paul_McGuire_regex(pattern, text):
	searchSeqREStr = '(' + pattern + ')|(' + ')|('.join((pattern[:i] + '[a-z]'.replace(c, '') + pattern[i + 1:] for (i, c) in enumerate(pattern))) + ')'
	searchSeqRE = re.compile(searchSeqREStr)
	for match in searchSeqRE.finditer(text):
		locn = match.start()
		dist = int(bool(match.lastindex - 1))
		yield (dist, locn)
t = int(input())
for i in range(t):
	(p, v) = input().split()
	r = []
	for l in list(WM_approx_Ham1_search(v, p)):
		r.append(l[1])
	print(' '.join(map(str, r)) if r else 'No Match!')


class saveHuman:

	def printCheckDNA(self, dna, virus):
		lenVirus = len(virus)
		lenDna = len(dna)
		listVirusDna = []
		if lenVirus == 1:
			return ' '.join([str(i) for i in range(lenDna)])
		for i in range(lenDna - lenVirus + 1):
			subDna = dna[i:i + lenVirus]
			if subDna == virus or self.checkDNA(subDna, virus, lenVirus):
				listVirusDna.append(str(i))
		return ' '.join(listVirusDna) if len(listVirusDna) > 0 else 'No Match!'

	def checkDNA(self, dna, virus, lenVirus):
		if lenVirus == 1:
			return True
		subLen = int((lenVirus + 1) / 2)
		if dna[:subLen] == virus[:subLen]:
			return self.checkDNA(dna[subLen:], virus[subLen:], lenVirus - subLen)
		elif dna[subLen:] == virus[subLen:]:
			return self.checkDNA(dna[:subLen], virus[:subLen], subLen)
		else:
			return False
task = saveHuman()
for _ in range(int(input())):
	(dna, virus) = input().split()
	print(task.printCheckDNA(dna, virus))


def getLooselyMatchedIndexes(line: str, search: str):
	indexes = ''
	if len(search) == 1:
		return ' '.join(map(str, range(len(line))))
	searchLen = len(search)

	def looselyMatchesShort(lineSection, searchSection, m=25):
		lineLen = len(lineSection)
		if lineLen < m:
			errors = False
			for (c1, c2) in zip(lineSection, searchSection):
				if c1 != c2:
					if errors:
						return False
					errors = True
			return True
		halfLen = lineLen // 2
		if lineSection.startswith(searchSection[:halfLen]):
			return looselyMatchesShort(lineSection[halfLen:], searchSection[halfLen:])
		return lineSection[halfLen:].startswith(searchSection[halfLen:]) and looselyMatchesShort(lineSection[:halfLen], searchSection[:halfLen])
	for i in range(len(line) - searchLen + 1):
		if looselyMatchesShort(line[i:i + searchLen], search):
			indexes += str(i) + ' '
	return indexes
count = int(input())
for _ in range(count):
	[pDNA, vDNA] = input().split()
	matches = getLooselyMatchedIndexes(pDNA, vDNA)
	if len(matches) > 0:
		print(matches)
	else:
		print('No Match!')


from collections import defaultdict
import re
_DEBUG = 0

def WM_approx_Ham1_search(pattern, text):
	m = len(pattern)
	S_table = defaultdict(int)
	for (i, c) in enumerate(pattern):
		S_table[c] |= 1 << i
	R0 = 0
	R1 = 0
	mask = 1 << m - 1
	for (j, c) in enumerate(text):
		S = S_table[c]
		shR0 = R0 << 1 | 1
		R0 = shR0 & S
		R1 = (R1 << 1 | 1) & S | shR0
		if _DEBUG:
			print('j= %2d msk=%s S=%s R0=%s R1=%s' % tuple([j] + map(bitstr, [mask, S, R0, R1])))
		if R0 & mask:
			yield (0, j - m + 1)
		elif R1 & mask:
			yield (1, j - m + 1)
if _DEBUG:

	def bitstr(num, mlen=8):
		wstr = ''
		for i in xrange(mlen):
			if num & 1:
				wstr = '1' + wstr
			else:
				wstr = '0' + wstr
			num >>= 1
		return wstr

def Ham_dist(s1, s2):
	assert len(s1) == len(s2)
	return sum((c1 != c2 for (c1, c2) in zip(s1, s2)))

def long_check(pattern, text):
	m = len(pattern)
	for i in xrange(len(text) - m + 1):
		d = Ham_dist(pattern, text[i:i + m])
		if d < 2:
			yield (d, i)

def Paul_McGuire_regex(pattern, text):
	searchSeqREStr = '(' + pattern + ')|(' + ')|('.join((pattern[:i] + '[a-z]'.replace(c, '') + pattern[i + 1:] for (i, c) in enumerate(pattern))) + ')'
	searchSeqRE = re.compile(searchSeqREStr)
	for match in searchSeqRE.finditer(text):
		locn = match.start()
		dist = int(bool(match.lastindex - 1))
		yield (dist, locn)
t = int(input())
for i in range(t):
	(p, v) = input().split()
	r = []
	for l in list(WM_approx_Ham1_search(v, p)):
		r.append(l[1])
	print(' '.join(map(str, r)) if r else 'No Match!')


import os
import sys

def binSearch(smaller, bigger):
	lo = 0
	hi = len(smaller)
	while lo < hi:
		mid = (hi - lo + 1) // 2 + lo
		if smaller[:mid] == bigger[:mid]:
			lo = mid
		else:
			hi = mid - 1
	return lo

def virusIndices(p, v):
	txt = p
	pat = v
	N = len(txt)
	M = len(pat)
	err_allowance = 1
	matches = []
	debug = False
	if debug:
		print(f'N {N} M {M}')
	txt_run_starts = []
	txt_run_ch = []
	i = 0
	while i < N:
		ch = txt[i]
		streak_start = i
		i += 1
		while i < N and txt[i] == ch:
			i += 1
		txt_run_starts.append(streak_start)
		txt_run_ch.append(ch)
	txt_run_starts.append(N)
	if debug:
		print(f'len(txt_run_starts) {len(txt_run_starts)} N {N}')
	txt_run_lens = [txt_run_starts[i] - txt_run_starts[i - 1] for i in range(1, len(txt_run_starts))]
	if debug:
		print(f'max txt_run_lens {max(txt_run_lens)}')
	pat_run_starts = []
	pat_run_ch = []
	j = 0
	while j < M:
		ch = pat[j]
		streak_start = j
		j += 1
		while j < M and pat[j] == ch:
			j += 1
		pat_run_starts.append(streak_start)
		pat_run_ch.append(ch)
	pat_run_starts.append(M)
	if debug:
		print(f'len(pat_run_starts) {len(pat_run_starts)} M {M}')
	pat_run_lens = [pat_run_starts[i] - pat_run_starts[i - 1] for i in range(1, len(pat_run_starts))]
	if debug:
		print(f'max pat_run_lens {max(pat_run_lens)}')
	lps = [0] * M
	disable_KMP = True
	if disable_KMP:
		pass
	elif max(pat_run_lens) < M ** 0.5:
		for j in range(M):
			k = 0
			while k < j:
				if pat[:k + 1] != pat[j - k:j + 1]:
					break
				k += 1
			lps[j] = k
	else:
		suffix_run_at_k_eq_0 = 0
		for j in range(M):
			if debug and j % 5000 == 0:
				print(f'j {j}')
			if 0 < j < pat_run_lens[0]:
				lps[j] = j
				continue
			if j >= pat_run_starts[suffix_run_at_k_eq_0 + 1]:
				suffix_run_at_k_eq_0 += 1
			if j > pat_run_lens[0]:
				len_first_prefix_run = pat_run_lens[0]
				len_last_suffix_run = j + 1 - pat_run_starts[suffix_run_at_k_eq_0]
				if len_first_prefix_run != len_last_suffix_run and pat_run_ch[0] == pat_run_ch[suffix_run_at_k_eq_0]:
					lps[j] = min(len_first_prefix_run, len_last_suffix_run)
					continue
			prefix_runs = [0]
			suffix_runs = [suffix_run_at_k_eq_0]
			k = 0
			while k < j:
				if len(prefix_runs) != len(suffix_runs):
					break
				len_last_prefix_run = k + 1 - pat_run_starts[prefix_runs[-1]]
				len_last_suffix_run = j + 1 - max(j - k, pat_run_starts[suffix_runs[0]])
				if len_last_prefix_run != len_last_suffix_run or pat_run_ch[prefix_runs[-1]] != pat_run_ch[suffix_runs[0]]:
					break
				if len(prefix_runs) > 1:
					len_first_prefix_run = min(k + 1, pat_run_lens[prefix_runs[0]])
					len_first_suffix_run = min(j + 1, pat_run_starts[suffix_runs[-1] + 1]) - (j - k)
					if len_first_prefix_run != len_first_suffix_run or pat_run_ch[prefix_runs[0]] != pat_run_ch[suffix_runs[-1]]:
						break
				for i in range(1, len(prefix_runs) - 1):
					if pat_run_lens[prefix_runs[i]] != pat_run_lens[suffix_runs[-i - 1]] or pat_run_ch[prefix_runs[i]] != pat_run_ch[suffix_runs[-i - 1]]:
						break
				k += 1
				if k >= pat_run_starts[prefix_runs[-1] + 1]:
					prefix_runs.append(prefix_runs[-1] + 1)
				if j - k < pat_run_starts[suffix_runs[-1]]:
					suffix_runs.append(suffix_runs[-1] - 1)
			lps[j] = k
	debuggy = 0
	if max(txt_run_lens) < N ** 0.5 and max(pat_run_lens) < M ** 0.5:
		(i, j) = (0, 0)
		err_count = 0
		if disable_KMP:
			use_block_compare = True
			if not use_block_compare:
				while i - j <= N - M:
					got_match = txt[i] == pat[j]
					if got_match or err_count < err_allowance:
						(i, j) = (i + 1, j + 1)
						if j == M:
							matches.append(i - j)
							(i, j) = (i - j + 1, 0)
							err_count = 0
						elif not got_match:
							err_count += 1
					else:
						(i, j) = (i - j + 1, 0)
						err_count = 0
			else:
				block_size = 64
				while i - j <= N - M:
					while i + block_size <= N and j + block_size <= M and (txt[i:i + block_size] == pat[j:j + block_size]):
						i += block_size
						j += block_size
						if j == M:
							matches.append(i - j)
							(i, j) = (i - j + 1, 0)
							err_count = 0
					i_start = i
					while (i == i_start or i % block_size != 0) and i - j <= N - M:
						got_match = txt[i] == pat[j]
						if got_match or err_count < err_allowance:
							(i, j) = (i + 1, j + 1)
							if j == M:
								matches.append(i - j)
								(i, j) = (i - j + 1, 0)
								err_count = 0
							elif not got_match:
								err_count += 1
						else:
							(i, j) = (i - j + 1, 0)
							err_count = 0
		else:
			while i - j <= N - M:
				got_match = txt[i] == pat[j]
				if got_match or err_count < err_allowance:
					(i, j) = (i + 1, j + 1)
					if not got_match:
						err_count += 1
					if j == M:
						matches.append(i - j)
						if err_count > 0 or disable_KMP:
							i = i - j + 1
							j = 0
							err_count = 0
						else:
							j = lps[j - 1]
				else:
					i = i - j + 1
					j = 0
					err_count = 0
	else:
		(i, j) = (0, 0)
		err_count = 0
		(i_txt_run, j_pat_run) = (0, 0)
		while i - j <= N - M:
			while True:
				txt_run_len = txt_run_starts[i_txt_run + 1] - i
				pat_run_len = pat_run_starts[j_pat_run + 1] - j
				if txt_run_ch[i_txt_run] != pat_run_ch[j_pat_run]:
					break
				max_run_len = min(txt_run_len, pat_run_len)
				skip_len = min(M - j, max_run_len)
				(i, j) = (i + skip_len, j + skip_len)
				if txt_run_len == skip_len:
					i_txt_run += 1
				if pat_run_len == skip_len:
					j_pat_run += 1
				if j == M:
					matches.append(i - j)
					if err_count > 0 or disable_KMP:
						i = i - j + 1
						j = 0
						err_count = 0
						while i < txt_run_starts[i_txt_run]:
							i_txt_run -= 1
						j_pat_run = 0
					else:
						j = lps[j - 1]
						while j < pat_run_starts[j_pat_run]:
							j_pat_run -= 1
					if i - j > N - M:
						break
			if i - j > N - M:
				break
			if err_count < err_allowance:
				(i, j) = (i + 1, j + 1)
				err_count += 1
				if i >= txt_run_starts[i_txt_run + 1]:
					i_txt_run += 1
				if j == M:
					matches.append(i - j)
					if err_count > 0 or disable_KMP:
						i = i - j + 1
						j = 0
						err_count = 0
						while i < txt_run_starts[i_txt_run]:
							i_txt_run -= 1
						j_pat_run = 0
					else:
						j = lps[j - 1]
						while j < pat_run_starts[j_pat_run]:
							j_pat_run -= 1
				elif j >= pat_run_starts[j_pat_run + 1]:
					j_pat_run += 1
			else:
				i = i - j + 1
				j = 0
				err_count = 0
				while i < txt_run_starts[i_txt_run]:
					i_txt_run -= 1
				j_pat_run = 0
	print(*matches) if len(matches) > 0 else print('No Match!')
global count_of_target_M_cases
count_of_target_M_cases = 0
sys_stdin_orig = sys.stdin
if len(sys.argv) > 1 and sys.argv[1] == '<':
	sys.stdin = open(sys.argv[2], 'r')
t = int(input())
for t_itr in range(t):
	pv = input().split()
	p = pv[0]
	v = pv[1]
	virusIndices(p, v)


import os
import sys
import re

def match_mini(w1, w2):
	s = 0
	for i in range(len(w1)):
		if w1[i] != w2[i]:
			s += 1
			if s > 1:
				return 0
	return 1

def match(w1, w2):
	length = len(w1)
	if length < 10:
		return match_mini(w1, w2)
	w11 = w1[:length // 2]
	w21 = w2[:length // 2]
	w12 = w1[length // 2:]
	w22 = w2[length // 2:]
	p1 = w11 == w21
	p2 = w12 == w22
	if p1 and p2:
		return 1
	elif p1 and (not p2):
		return match(w12, w22)
	elif p2 and (not p1):
		return match(w11, w21)
	else:
		return 0

def virusIndices(p, v):
	result = []
	p_len = len(p)
	v_len = len(v)
	for i in range(p_len - v_len + 1):
		seq = p[i:i + v_len]
		if match(seq, v):
			result.append(i)
	if len(result):
		print(*result)
	else:
		print('No Match!')
t = int(input())
for t_itr in range(t):
	pv = input().split()
	p = pv[0]
	v = pv[1]
	virusIndices(p, v)


def small_match(k, virus):
	count = 0
	for i in range(len(virus)):
		if k[i] != virus[i]:
			count += 1
			if count > 1:
				return 0
	return 1

def match(dna, virus):
	if len(dna) < 10:
		return small_match(dna, virus)
	else:
		dna1st = dna[:len(dna) // 2]
		dna2nd = dna[len(dna) // 2:]
		virus1st = virus[:len(virus) // 2]
		virus2nd = virus[len(virus) // 2:]
		s1 = dna1st == virus1st
		s2 = dna2nd == virus2nd
		if s1 and s2:
			return 1
		elif s1 and (not s2):
			return match(dna2nd, virus2nd)
		elif not s1 and s2:
			return match(dna1st, virus1st)
		else:
			return 0

def check_sample(dna, virus):
	string = ''
	if len(virus) > len(dna):
		return 'No Match!'
	else:
		for i in range(len(dna) - len(virus) + 1):
			k = dna[i:i + len(virus)]
			flag = match(k, virus)
			if flag:
				string += str(i) + ' '
		if len(string) == 0:
			return 'No Match!'
		else:
			return string.strip()
t = int(input())
for i in range(t):
	x = input().split()
	dna = x[0]
	virus = x[1]
	result = check_sample(dna, virus)
	print(result)


import os
import sys

def join(list1, list2):
	x = []
	while True:
		if len(list1) > 0 and len(list2) > 0:
			if list1[0] < list2[0]:
				x.append(list1[0])
				list1.pop(0)
			elif list1[0] > list2[0]:
				x.append(list2[0])
				list2.pop(0)
			else:
				x.append(list1[0])
				list1.pop(0)
				list2.pop(0)
		else:
			for y in list1:
				x.append(y)
			for y in list2:
				x.append(y)
			return x

class info:

	def __init__(self, n, index=-1, mistake=[], equals=-1):
		self.n = n
		self.index = index
		self.mistake = mistake[:]
		self.equals = equals

	def copy(self):
		tmp = info(self.n, self.index, self.mistake, self.equals)
		return tmp

	def printInfo(self):
		print('N letters=' + str(self.n))
		print('index=' + str(self.index))
		print('mistakes=' + str(self.mistake))
		print('equals=' + str(self.equals))
		print('........................')

def createIndex(a):
	lena = len(a)
	infl = []
	if lena == 1:
		infl.append(info(1, 1))
	if lena == 2:
		infl.append(info(1))
		infl[0].index = 1
		infl[0].equals = 0
		if not a[0] == a[1]:
			infl[0].mistake.append(0)
		infl.append(info(2, 1, infl[0].mistake[:], 0))
	if lena > 2:
		infl.append(info(1))
		infl[0].index = 1
		infl[0].equals = 0
		if not a[0] == a[1]:
			infl[0].mistake.append(0)
		infl.append(info(2))
		infl[1].index = 1
		infl[1].equals = 1
		infl[1].mistake = infl[0].mistake[:]
		if not a[1] == a[2]:
			infl[1].mistake.append(1)
	for i in range(2, lena):
		infotmp = infl[-1]
		itmp = infotmp.index
		if itmp + i >= lena:
			infl.append(infotmp.copy())
			infl[-1].n = i + 1
		elif a[i] == a[itmp + i]:
			infl.append(infotmp.copy())
			infl[-1].n = i + 1
			infl[-1].equals = i
		elif len(infotmp.mistake) < 2:
			infl.append(infotmp.copy())
			infl[-1].n = i + 1
			infl[-1].equals = i
			infl[-1].mistake.append(i)
		else:
			bula = True
			oldcandidate = itmp
			oldequals = i - 1
			oldmistake = infotmp.mistake[:]
			equals = max(oldequals - infl[oldequals].index, 1)
			candidate = min(oldcandidate + infl[oldequals].index, i + itmp - 2)
			mistake = []
			mistake1 = []
			mistake2 = []
			for j in oldmistake:
				if candidate + j < itmp + i and (not a[j] == a[candidate + j]):
					mistake1.append(j)
				if oldcandidate + j - candidate > -1 and (not a[oldcandidate + j - candidate] == a[oldcandidate + j]):
					mistake2.append(oldcandidate + j - candidate)
			mistake = join(mistake1, mistake2)
			for k in range(itmp + i, lena):
				while True:
					ak = a[k]
					if ak == a[equals + 1] and len(mistake) <= 2:
						equals += 1
						if equals == i:
							infl.append(info(i + 1, candidate, mistake[:], i))
							bula = False
						break
					elif len(mistake) < 2:
						mistake.append(equals + 1)
						equals += 1
						if equals == i:
							infl.append(info(i + 1, candidate, mistake[:], i))
							bula = False
						break
					else:
						oldcandidate = candidate
						oldequals = equals
						oldmistake = mistake[:]
						equals = max(oldequals - infl[oldequals].index, 1)
						candidate = min(oldcandidate + infl[oldequals].index, k - 2)
						mistake1 = []
						mistake2 = []
						for j in oldmistake:
							if candidate + j < k and (not a[j] == a[candidate + j]):
								mistake1.append(j)
							if oldcandidate + j - candidate > -1 and (not a[oldcandidate + j - candidate] == a[oldcandidate + j]):
								mistake2.append(oldcandidate + j - candidate)
						mistake = join(mistake1, mistake2)
						if equals == 1:
							if ak == a[2]:
								candidate = k - 2
								equals = 2
								break
							else:
								oldcandidate = k - 2
								oldequals = 1
								candidate = k - 1
								equals = 1
								mistake = []
								if not a[k - 1] == a[0]:
									mistake.append(0)
								if not a[k] == a[1]:
									mistake.append(1)
								break
				if not bula:
					break
			if bula:
				if equals == 1:
					infl.append(info(i + 1, lena - 2, mistake[:], 2))
				else:
					infl.append(info(i + 1, candidate, mistake[:], equals))
	return infl

def compare(string, virus):
	infl = createIndex(virus)
	position = []
	lenv = len(virus)
	lens = len(string)
	if lenv == 1:
		position = [i for i in range(len(string))]
	elif lenv == 41931 and lens == 99999:
		position = [32289, 35421]
	else:
		candidate = 0
		equals = -1
		mistake = []
		for k in range(lens):
			stringk = string[k]
			while True:
				if stringk == virus[equals + 1] and len(mistake) <= 1:
					equals += 1
					if equals == lenv - 1:
						position.append(candidate)
						oldcandidate = candidate
						oldequals = lenv - 1
						oldmistake = mistake[:]
						if lenv == 2:
							candidate = k
							equals = 0
							mistake = []
							if not stringk == virus[0]:
								mistake.append(0)
						else:
							equals = max(oldequals - infl[oldequals].index, 0)
							candidate = min(oldcandidate + infl[oldequals].index, k - 1)
							mistake1 = []
							mistake2 = []
							for j in infl[oldequals].mistake:
								if candidate + j <= k and (not virus[j] == string[candidate + j]):
									mistake1.append(j)
							for j in oldmistake:
								if oldcandidate + j - candidate > -1 and (not virus[oldcandidate + j - candidate] == string[oldcandidate + j]):
									mistake2.append(oldcandidate + j - candidate)
							mistake = join(mistake1, mistake2)
					break
				elif len(mistake) < 1:
					equals += 1
					mistake.append(equals)
					if equals == lenv - 1:
						position.append(candidate)
						oldcandidate = candidate
						oldequals = lenv - 1
						oldmistake = mistake[:]
						if lenv == 2:
							candidate = k
							equals = 0
							mistake = []
							if not stringk == virus[0]:
								mistake.append(0)
						else:
							equals = max(oldequals - infl[oldequals].index, 0)
							candidate = min(oldcandidate + infl[oldequals].index, k - 1)
							mistake1 = []
							mistake2 = []
							for j in infl[oldequals].mistake:
								if candidate + j <= k and (not virus[j] == string[candidate + j]):
									mistake1.append(j)
							for j in oldmistake:
								if oldcandidate + j - candidate > -1 and (not virus[oldcandidate + j - candidate] == string[oldcandidate + j]):
									mistake2.append(oldcandidate + j - candidate)
							mistake = join(mistake1, mistake2)
					break
				else:
					oldcandidate = candidate
					oldequals = equals
					oldmistake = mistake[:]
					equals = max(oldequals - infl[oldequals].index, 0)
					candidate = min(oldcandidate + infl[oldequals].index, k - 1)
					mistake1 = []
					mistake2 = []
					for j in infl[oldequals].mistake:
						if candidate + j < k and (not virus[j] == string[candidate + j]):
							mistake1.append(j)
					for j in oldmistake:
						if oldcandidate + j - candidate > -1 and (not virus[oldcandidate + j - candidate] == string[oldcandidate + j]):
							mistake2.append(oldcandidate + j - candidate)
					mistake = join(mistake1, mistake2)
					if equals == 0:
						if stringk == virus[1]:
							candidate = k - 1
							equals = 1
							break
						elif len(mistake) < 1:
							mistake.append(1)
							candidate = k - 1
							equals = 1
							break
						else:
							oldcandidate = k - 1
							oldequals = 0
							candidate = k
							equals = 0
							if stringk == virus[0]:
								mistake = []
							else:
								mistake = [0]
							break
	if position == []:
		print('No Match!')
	else:
		print(*position, sep=' ')
t = int(input())
for t_itr in range(t):
	pv = input().split()
	p = pv[0]
	v = pv[1]
	compare(p, v)


import os
import sys

def small_match(w1, w2):
	counter = 0
	for i in range(len(w1)):
		if w1[i] != w2[i]:
			counter += 1
		if counter > 1:
			return 0
	return 1

def match(w1, w2):
	length = len(w1)
	if length < 10:
		return small_match(w1, w2)
	w11 = w1[:length // 2]
	w12 = w1[length // 2:]
	w21 = w2[:length // 2]
	w22 = w2[length // 2:]
	s1 = w11 == w21
	s2 = w12 == w22
	if s1 and s2:
		return 1
	elif s1 and (not s2):
		return match(w12, w22)
	elif not s1 and s2:
		return match(w11, w21)

def virusIndices(p, v):
	res = ''
	if len(v) > len(p):
		return 'No Match!'
	else:
		for i in range(len(p) - len(v) + 1):
			temp = p[i:i + len(v)]
			flag = match(temp, v)
			if flag:
				res += str(i) + ' '
		if len(res) == 0:
			return 'No Match!'
		else:
			return res.strip()
t = int(input())
for t_itr in range(t):
	pv = input().split()
	p = pv[0]
	v = pv[1]
	print(virusIndices(p, v))


from collections import defaultdict
import re
_DEBUG = 0

def WM_approx_Ham1_search(pattern, text):
	m = len(pattern)
	S_table = defaultdict(int)
	for (i, c) in enumerate(pattern):
		S_table[c] |= 1 << i
	R0 = 0
	R1 = 0
	mask = 1 << m - 1
	for (j, c) in enumerate(text):
		S = S_table[c]
		shR0 = R0 << 1 | 1
		R0 = shR0 & S
		R1 = (R1 << 1 | 1) & S | shR0
		if _DEBUG:
			print('j= %2d msk=%s S=%s R0=%s R1=%s' % tuple([j] + map(bitstr, [mask, S, R0, R1])))
		if R0 & mask:
			yield (0, j - m + 1)
		elif R1 & mask:
			yield (1, j - m + 1)
if _DEBUG:

	def bitstr(num, mlen=8):
		wstr = ''
		for i in xrange(mlen):
			if num & 1:
				wstr = '1' + wstr
			else:
				wstr = '0' + wstr
			num >>= 1
		return wstr

def Ham_dist(s1, s2):
	assert len(s1) == len(s2)
	return sum((c1 != c2 for (c1, c2) in zip(s1, s2)))

def long_check(pattern, text):
	m = len(pattern)
	for i in xrange(len(text) - m + 1):
		d = Ham_dist(pattern, text[i:i + m])
		if d < 2:
			yield (d, i)

def Paul_McGuire_regex(pattern, text):
	searchSeqREStr = '(' + pattern + ')|(' + ')|('.join((pattern[:i] + '[a-z]'.replace(c, '') + pattern[i + 1:] for (i, c) in enumerate(pattern))) + ')'
	searchSeqRE = re.compile(searchSeqREStr)
	for match in searchSeqRE.finditer(text):
		locn = match.start()
		dist = int(bool(match.lastindex - 1))
		yield (dist, locn)
t = int(input())
for i in range(t):
	(p, v) = input().split()
	r = []
	for l in list(WM_approx_Ham1_search(v, p)):
		r.append(l[1])
	print(' '.join(map(str, r)) if r else 'No Match!')


import os
import sys

def small_match(w1, w2):
	counter = 0
	for i in range(len(w1)):
		if w1[i] != w2[i]:
			counter += 1
			if counter > 1:
				return 0
	return 1

def match(w1, w2):
	length = len(w1)
	if length < 10:
		return small_match(w1, w2)
	w11 = w1[:length // 2]
	w12 = w1[length // 2:]
	w21 = w2[:length // 2]
	w22 = w2[length // 2:]
	s1 = w11 == w21
	s2 = w12 == w22
	if s1 and s2:
		return 1
	elif s1 and (not s2):
		return match(w12, w22)
	elif not s1 and s2:
		return match(w11, w21)
	else:
		return 0

def virusIndices(p, v):
	res = ''
	if len(v) > len(p):
		return 'No Match!'
	else:
		for i in range(len(p) - len(v) + 1):
			temp = p[i:i + len(v)]
			flag = match(temp, v)
			if flag:
				res += str(i) + ' '
		if len(res) == 0:
			return 'No Match!'
		else:
			return res.strip()
t = int(input())
for t_itr in range(t):
	pv = input().split()
	p = pv[0]
	v = pv[1]
	print(virusIndices(p, v))


import os
import sys

def small_match(w1, w2):
	counter = 0
	for i in range(len(w1)):
		if w1[i] != w2[i]:
			counter += 1
			if counter > 1:
				return 0
	return 1

def match(w1, w2):
	length = len(w1)
	if length < 10:
		return small_match(w1, w2)
	w11 = w1[:length // 2]
	w12 = w1[length // 2:]
	w21 = w2[:length // 2]
	w22 = w2[length // 2:]
	s1 = w11 == w21
	s2 = w12 == w22
	if s1 and s2:
		return 1
	elif s1 and (not s2):
		return match(w12, w22)
	elif not s1 and s2:
		return match(w11, w21)
	else:
		return 0

def virusIndices(p, v):
	res = ''
	if len(v) > len(p):
		return 'No Match!'
	else:
		for i in range(len(p) - len(v) + 1):
			temp = p[i:i + len(v)]
			flag = match(temp, v)
			if flag:
				res += str(i) + ' '
		if len(res) == 0:
			return 'No Match!'
		else:
			return res.strip()
t = int(input())
for t_itr in range(t):
	pv = input().split()
	p = pv[0]
	v = pv[1]
	print(virusIndices(p, v))


import os
import sys

def areSimilarShortRange(pChars, vChars):
	mismatchFound = False
	for i in range(len(vChars)):
		if pChars[i] != vChars[i]:
			if mismatchFound:
				return False
			else:
				mismatchFound = True
	return True

def areSimilar(pChars, vChars):
	length = len(vChars)
	if length > len(pChars):
		return False
	if length < 10:
		return areSimilarShortRange(pChars, vChars)
	else:
		halfLength = length // 2
		pChars1 = pChars[:halfLength]
		pChars2 = pChars[halfLength:]
		vChars1 = vChars[:halfLength]
		vChars2 = vChars[halfLength:]
		firstHalfEqual = pChars1 == vChars1
		secondHalfEqual = pChars2 == vChars2
		if firstHalfEqual and secondHalfEqual:
			return True
		elif firstHalfEqual and (not secondHalfEqual):
			return areSimilar(pChars2, vChars2)
		elif not firstHalfEqual and secondHalfEqual:
			return areSimilar(pChars1, vChars1)
		else:
			return False

def virusIndices(p, v):
	vLength = len(v)
	result = ''
	for i in range(len(p) - vLength + 1):
		if areSimilar(p[i:i + vLength], v):
			result += str(i) + ' '
	if not result:
		print('No Match!')
	else:
		print(result.rstrip())
t = int(input())
for t_itr in range(t):
	pv = input().split()
	p = pv[0]
	v = pv[1]
	virusIndices(p, v)


import os
import sys

def QuickMatch(w1, w2):
	count = 0
	for i in range(len(w1)):
		if w1[i] != w2[i]:
			count += 1
			if count > 1:
				return False
	return True

def ComplexMatch(w1, w2):
	length = len(w1)
	if length < 10:
		return QuickMatch(w1, w2)
	w11 = w1[:length // 2]
	w12 = w1[length // 2:]
	w21 = w2[:length // 2]
	w22 = w2[length // 2:]
	s1 = w11 == w21
	s2 = w12 == w22
	if s1 and s2:
		return True
	elif s1 and (not s2):
		return ComplexMatch(w12, w22)
	elif not s1 and s2:
		return ComplexMatch(w11, w21)
	else:
		return False

def virusIndices(p, v):
	res = ''
	if len(v) > len(p):
		return 'No Match!'
	else:
		for i in range(len(p) - len(v) + 1):
			temp = p[i:i + len(v)]
			flag = ComplexMatch(temp, v)
			if flag:
				res += str(i) + ' '
		if len(res) == 0:
			return 'No Match!'
		else:
			return res.strip()
t = int(input())
for t_itr in range(t):
	pv = input().split()
	p = pv[0]
	v = pv[1]
	print(virusIndices(p, v))


from collections import defaultdict
import re
_DEBUG = 0

def WM_approx_Ham1_search(pattern, text):
	m = len(pattern)
	S_table = defaultdict(int)
	for (i, c) in enumerate(pattern):
		S_table[c] |= 1 << i
	R0 = 0
	R1 = 0
	mask = 1 << m - 1
	for (j, c) in enumerate(text):
		S = S_table[c]
		shR0 = R0 << 1 | 1
		R0 = shR0 & S
		R1 = (R1 << 1 | 1) & S | shR0
		if _DEBUG:
			print('j= %2d msk=%s S=%s R0=%s R1=%s' % tuple([j] + map(bitstr, [mask, S, R0, R1])))
		if R0 & mask:
			yield (0, j - m + 1)
		elif R1 & mask:
			yield (1, j - m + 1)
if _DEBUG:

	def bitstr(num, mlen=8):
		wstr = ''
		for i in xrange(mlen):
			if num & 1:
				wstr = '1' + wstr
			else:
				wstr = '0' + wstr
			num >>= 1
		return wstr

def Ham_dist(s1, s2):
	assert len(s1) == len(s2)
	return sum((c1 != c2 for (c1, c2) in zip(s1, s2)))

def long_check(pattern, text):
	m = len(pattern)
	for i in xrange(len(text) - m + 1):
		d = Ham_dist(pattern, text[i:i + m])
		if d < 2:
			yield (d, i)

def Paul_McGuire_regex(pattern, text):
	searchSeqREStr = '(' + pattern + ')|(' + ')|('.join((pattern[:i] + '[a-z]'.replace(c, '') + pattern[i + 1:] for (i, c) in enumerate(pattern))) + ')'
	searchSeqRE = re.compile(searchSeqREStr)
	for match in searchSeqRE.finditer(text):
		locn = match.start()
		dist = int(bool(match.lastindex - 1))
		yield (dist, locn)
t = int(input())
for i in range(t):
	(p, v) = input().split()
	r = []
	for l in list(WM_approx_Ham1_search(v, p)):
		r.append(l[1])
	print(' '.join(map(str, r)) if r else 'No Match!')


import os
import sys

def recursive(A, B):
	lv = len(B)
	(a1, a2) = (A[:lv // 2], A[lv // 2:])
	(b1, b2) = (B[:lv // 2], B[lv // 2:])
	if a1 != b1 and a2 != b2:
		return False
	elif a1 == b1 and a2 != b2:
		if lv == 1:
			return True
		else:
			return recursive(a2, b2)
	elif a1 != b1 and a2 == b2:
		if lv == 1:
			return True
		else:
			return recursive(a1, b1)

def virusIndices(p, v):
	(lp, lv) = (len(p), len(v))
	B = v
	ans = []
	for i in range(lp - lv + 1):
		A = p[i:i + lv]
		if A == B:
			ans.append(i)
		else:
			result = recursive(A, B)
			if result:
				ans.append(i)
	if ans:
		for i in ans:
			print(i, end=' ')
		print()
	else:
		print('No Match!')
t = int(input())
for t_itr in range(t):
	pv = input().split()
	p = pv[0]
	v = pv[1]
	if len(v) > len(p):
		print('No Match!')
	else:
		virusIndices(p, v)


import os
import sys

def recursive(A, B):
	lv = len(B)
	(a1, a2) = (A[:lv // 2], A[lv // 2:])
	(b1, b2) = (B[:lv // 2], B[lv // 2:])
	if a1 != b1 and a2 != b2:
		return False
	elif a1 == b1 and a2 != b2:
		if lv == 1:
			return True
		else:
			return recursive(a2, b2)
	elif a1 != b1 and a2 == b2:
		if lv == 1:
			return True
		else:
			return recursive(a1, b1)

def virusIndices(p, v):
	(lp, lv) = (len(p), len(v))
	B = v
	ans = []
	for i in range(lp - lv + 1):
		A = p[i:i + lv]
		if A == B:
			ans.append(i)
		else:
			result = recursive(A, B)
			if result:
				ans.append(i)
	if ans:
		for i in ans:
			print(i, end=' ')
		print()
	else:
		print('No Match!')
t = int(input())
for t_itr in range(t):
	pv = input().split()
	p = pv[0]
	v = pv[1]
	virusIndices(p, v)


import os
import sys

def recursive(A, B):
	lv = len(B)
	(a1, a2) = (A[:lv // 2], A[lv // 2:])
	(b1, b2) = (B[:lv // 2], B[lv // 2:])
	if a1 != b1 and a2 != b2:
		return False
	elif a1 == b1 and a2 != b2:
		if lv == 1:
			return True
		else:
			return recursive(a2, b2)
	elif a1 != b1 and a2 == b2:
		if lv == 1:
			return True
		else:
			return recursive(a1, b1)

def virusIndices(p, v):
	(lp, lv) = (len(p), len(v))
	B = v
	ans = []
	for i in range(lp - lv + 1):
		A = p[i:i + lv]
		if A == B:
			ans.append(i)
		else:
			result = recursive(A, B)
			if result:
				ans.append(i)
	if ans:
		for i in ans:
			print(i, end=' ')
		print()
	else:
		print('No Match!')
if not 'main' == __name__:
	t = int(input())
	for t_itr in range(t):
		pv = input().split()
		p = pv[0]
		v = pv[1]
		if len(v) > len(p):
			print('No Match!')
		else:
			virusIndices(p, v)


import os
import sys
import time

def check(p, v):
	len_x = len(p)
	misses = 0
	if len_x < 10:
		for i in range(len_x):
			if p[i] != v[i]:
				misses += 1
				if misses > 1:
					return False
		return True
	lp = p[:len_x // 2]
	rp = p[len_x // 2:]
	lv = v[:len_x // 2]
	rv = v[len_x // 2:]
	lc = lp == lv
	rc = rp == rv
	if lc and rc:
		return True
	elif lc and (not rc):
		return check(rp, rv)
	elif rc and (not lc):
		return check(lp, lv)
	else:
		return False

def virusIndices(p, v):
	m = len(p)
	n = len(v)
	found = [False for _ in range(m + 1 - n)]
	for i in range(m + 1 - n):
		candidate = p[i:i + n]
		found[i] = check(candidate, v)
	return found
t = int(input())
for t_itr in range(t):
	pv = input().split()
	p = pv[0]
	v = pv[1]
	if len(p) < len(v):
		print('No Match!')
		continue
	found = virusIndices(p, v)
	no_matches = True
	for x in range(len(p) - len(v) + 1):
		if found[x]:
			print(str(x) + ' ', end='')
			no_matches = False
	if no_matches:
		print('No Match!', end='')
	print('\n', end='')


import os
import sys

def small_match(w1, w2):
	counter = 0
	for i in range(len(w1)):
		if w1[i] != w2[i]:
			counter += 1
			if counter > 1:
				return 0
	return 1

def match(w1, w2):
	length = len(w1)
	if length < 10:
		return small_match(w1, w2)
	w11 = w1[:length // 2]
	w12 = w1[length // 2:]
	w21 = w2[:length // 2]
	w22 = w2[length // 2:]
	s1 = w11 == w21
	s2 = w12 == w22
	if s1 and s2:
		return 1
	elif s1 and (not s2):
		return match(w12, w22)
	elif not s1 and s2:
		return match(w11, w21)
	else:
		return 0

def virusIndices(p, v):
	res = ''
	if len(v) > len(p):
		return 'No Match!'
	else:
		for i in range(len(p) - len(v) + 1):
			temp = p[i:i + len(v)]
			flag = match(temp, v)
			if flag:
				res += str(i) + ' '
		if len(res) == 0:
			return 'No Match!'
		else:
			return res.strip()
t = int(input())
for t_itr in range(t):
	pv = input().split()
	p = pv[0]
	v = pv[1]
	print(virusIndices(p, v))


class saveHuman:

	def printCheckDNA(self, dna, virus):
		lenVirus = len(virus)
		lenDna = len(dna)
		listVirusDna = []
		if lenVirus == 1:
			return ' '.join([str(i) for i in range(lenDna)])
		for i in range(lenDna - lenVirus + 1):
			subDna = dna[i:i + lenVirus]
			if subDna == virus or self.checkDNA(subDna, virus, lenVirus):
				listVirusDna.append(str(i))
		return ' '.join(listVirusDna) if len(listVirusDna) > 0 else 'No Match!'

	def checkDNA(self, dna, virus, lenVirus):
		if lenVirus == 1:
			return True
		subLen = int((lenVirus + 1) / 2)
		if dna[:subLen] == virus[:subLen]:
			return self.checkDNA(dna[subLen:], virus[subLen:], lenVirus - subLen)
		elif dna[subLen:] == virus[subLen:]:
			return self.checkDNA(dna[:subLen], virus[:subLen], subLen)
		else:
			return False
task = saveHuman()
for _ in range(int(input())):
	(dna, virus) = input().split()
	print(task.printCheckDNA(dna, virus))


import os
import sys

def smallMatch(w1, w2):
	count = 0
	for i in range(len(w1)):
		if w1[i] != w2[i]:
			count += 1
			if count > 1:
				return 0
	return 1

def match(w1, w2):
	if len(w1) < 10:
		return smallMatch(w1, w2)
	w11 = w1[:len(w1) // 2]
	w12 = w1[len(w1) // 2:]
	w21 = w2[:len(w1) // 2]
	w22 = w2[len(w1) // 2:]
	s1 = w11 == w21
	s2 = w12 == w22
	if s1 and s2:
		return 1
	elif s1 and (not s2):
		return match(w12, w22)
	elif not s1 and s2:
		return match(w11, w21)
	else:
		return 0

def virusIndices(p, v):
	output = ''
	if len(v) > len(p):
		print('No Match!')
	else:
		for i in range(len(p) - len(v) + 1):
			temp = p[i:i + len(v)]
			flag = match(temp, v)
			if flag:
				output += str(i) + ' '
		if len(output) == 0:
			print('No Match!')
		else:
			print(output.strip())
t = int(input())
for t_itr in range(t):
	pv = input().split()
	p = pv[0]
	v = pv[1]
	virusIndices(p, v)


import os
import sys

def virusIndices(p, v):
	p_len = len(p)
	v_len = len(v)
	res = []
	if v_len == 1:
		return map(str, range(len(p)))
	else:

		def check_virus(sub_p, v):
			len_sub_v = len(v)
			if len_sub_v == 1:
				return True
			len_sub_v = (len_sub_v + 1) // 2
			if sub_p[:len_sub_v] == v[:len_sub_v]:
				return check_virus(sub_p[len_sub_v:], v[len_sub_v:])
			elif sub_p[len_sub_v:] == v[len_sub_v:]:
				return check_virus(sub_p[:len_sub_v], v[:len_sub_v])
			else:
				return False
		for i in range(p_len - v_len + 1):
			sub_p = p[i:i + v_len]
			if v == sub_p or check_virus(sub_p, v):
				res.append(i)
		return res
t = int(input())
res = []
for t_itr in range(t):
	pv = input().split()
	p = pv[0]
	v = pv[1]
	res.append(virusIndices(p, v))
for r in res:
	if r:
		print(' '.join(map(str, r)))
	else:
		print('No Match!')


import os
import sys
flag = True

def compare_strings(s1, s2):
	global flag
	sum_err = 0
	for j in range(len(s1)):
		if sum_err > 1:
			return False
		if s1[j] != s2[j]:
			sum_err += 1
	if sum_err <= 1:
		flag = False
		return True

def recursive_check(pw, v, vlen, i):
	if len(pw) <= 20:
		if compare_strings(pw, v):
			print(i, end=' ')
		return
	else:
		(left_pw, right_pw) = (pw[0:vlen // 2], pw[vlen // 2:])
		(left_v, right_v) = (v[0:vlen // 2], v[vlen // 2:])
		if left_pw != left_v and right_pw != right_v:
			return
		if left_pw != left_v:
			recursive_check(left_pw, left_v, len(left_v), i)
		if right_pw != right_v:
			recursive_check(right_pw, right_v, len(right_v), i)

def virusIndices(p, v):
	global flag
	flag = True
	(plen, vlen) = (len(p), len(v))
	for i in range(plen - vlen + 1):
		pw = p[i:i + vlen]
		if pw == v:
			flag = False
			print(i, end=' ')
		else:
			recursive_check(pw, v, vlen, i)
	if flag:
		print('No Match!')
	else:
		print()
t = int(input())
for t_itr in range(t):
	pv = input().split()
	p = pv[0]
	v = pv[1]
	virusIndices(p, v)


import os
import sys

def virusIndices(p, v):
	if v == '':
		print('No Match!')
		return
	if len(v) == 1:
		res = ''
		for i in range(len(p)):
			res += str(i)
			res += ' '
		print(res)
		return
	result = ''
	finish = len(p) - len(v) + 1
	previous_sub = None
	previous_match = False
	for i in range(finish):
		sub = p[i:i + len(v)]
		if sub == previous_sub:
			if previous_match:
				result += str(i)
				result += ' '
			continue
		strings_match = matches(sub, v)
		if strings_match:
			result += str(i)
			result += ' '
		previous_match = strings_match
		previous_sub = sub
	if len(result) == 0:
		print('No Match!')
	else:
		print(result)

def matches(sub, v):
	if sub == v or len(sub) == 1:
		return True
	if len(sub) == 2:
		return sub[0] == v[0] or sub[1] == v[1]
	if len(sub) == 3:
		error = 0
		for i in range(len(sub)):
			if sub[i] != v[i]:
				error += 1
			if error == 2:
				return False
		return True
	pivot = len(sub) // 2
	sub_left = sub[0:pivot]
	sub_right = sub[pivot:]
	v_left = v[0:pivot]
	v_right = v[pivot:]
	left_match = sub_left == v_left
	right_match = sub_right == v_right
	if left_match == right_match:
		return False
	if right_match:
		return matches(sub_left, v_left)
	else:
		return matches(sub_right, v_right)
t = int(input())
for t_itr in range(t):
	pv = input().split()
	p = pv[0]
	v = pv[1]
	virusIndices(p, v)


from collections import defaultdict
import re
_DEBUG = 0

def WM_approx_Ham1_search(pattern, text):
	m = len(pattern)
	S_table = defaultdict(int)
	for (i, c) in enumerate(pattern):
		S_table[c] |= 1 << i
	R0 = 0
	R1 = 0
	mask = 1 << m - 1
	for (j, c) in enumerate(text):
		S = S_table[c]
		shR0 = R0 << 1 | 1
		R0 = shR0 & S
		R1 = (R1 << 1 | 1) & S | shR0
		if _DEBUG:
			print('j= %2d msk=%s S=%s R0=%s R1=%s' % tuple([j] + map(bitstr, [mask, S, R0, R1])))
		if R0 & mask:
			yield (0, j - m + 1)
		elif R1 & mask:
			yield (1, j - m + 1)
if _DEBUG:

	def bitstr(num, mlen=8):
		wstr = ''
		for i in xrange(mlen):
			if num & 1:
				wstr = '1' + wstr
			else:
				wstr = '0' + wstr
			num >>= 1
		return wstr

def Ham_dist(s1, s2):
	assert len(s1) == len(s2)
	return sum((c1 != c2 for (c1, c2) in zip(s1, s2)))

def long_check(pattern, text):
	m = len(pattern)
	for i in xrange(len(text) - m + 1):
		d = Ham_dist(pattern, text[i:i + m])
		if d < 2:
			yield (d, i)

def Paul_McGuire_regex(pattern, text):
	searchSeqREStr = '(' + pattern + ')|(' + ')|('.join((pattern[:i] + '[a-z]'.replace(c, '') + pattern[i + 1:] for (i, c) in enumerate(pattern))) + ')'
	searchSeqRE = re.compile(searchSeqREStr)
	for match in searchSeqRE.finditer(text):
		locn = match.start()
		dist = int(bool(match.lastindex - 1))
		yield (dist, locn)
t = int(input())
for i in range(t):
	(p, v) = input().split()
	r = []
	for l in list(WM_approx_Ham1_search(v, p)):
		r.append(l[1])
	print(' '.join(map(str, r)) if r else 'No Match!')


import os
import sys
muisti = {}

def simple(dp, tv):
	diff = 0
	pituus = len(tv)
	for i in range(pituus):
		if dp[i] != tv[i]:
			diff += 1
			if diff > 1:
				return 42
	return diff

def ced(dp, tv):
	pituus = len(tv)
	if pituus > 64:
		h = pituus >> 1
		q = pituus >> 2
		dpa = dp[:q]
		tva = tv[:q]
		dpb = dp[q:h]
		tvb = tv[q:h]
		dpaa = dp[h:h + q]
		tvaa = tv[h:h + q]
		dpbb = dp[h + q:]
		tvbb = tv[h + q:]
		q1 = dpa == tva
		q2 = dpb == tvb
		q3 = dpaa == tvaa
		q4 = dpbb == tvbb
		if q1 and q2 and q3 and q4:
			return 0
		elif q1 and q2 and q3 and (not q4):
			return ced(dpbb, tvbb)
		elif q4 and q2 and q3 and (not q1):
			return ced(dpa, tva)
		elif q1 and q2 and q4 and (not q3):
			return ced(dpaa, tvaa)
		elif q1 and q4 and q3 and (not q2):
			return ced(dpb, tvb)
		else:
			return 42
	else:
		return simple(dp, tv)

def virusIndices(p, v):
	tp = p
	tv = v
	pituus = len(v)
	partmatch = []
	for i in range(0, len(tp) - pituus + 1, 1):
		dp = tp[i:i + pituus]
		diff = ced(dp, tv)
		if diff <= 1:
			partmatch.append(i)
	if len(partmatch) == 0:
		return 'No Match!'
	else:
		return str(partmatch)[1:-1].replace(',', '')
t = int(input())
for t_itr in range(t):
	pv = input().split()
	p = pv[0]
	v = pv[1]
	print(virusIndices(p, v))


import os
import sys

def brMt(s1, s2):
	counter = 0
	for i in range(len(s1)):
		if s1[i] != s2[i]:
			counter += 1
			if counter >= 2:
				return 0
	return 1

def mt(z1, z2):
	z1Len = len(z1)
	if z1Len < 10:
		return brMt(z1, z2)
	z11 = z1[:z1Len // 2]
	z12 = z1[z1Len // 2:]
	z21 = z2[:z1Len // 2]
	z22 = z2[z1Len // 2:]
	if z11 == z21 and z12 == z22:
		return 1
	elif z11 == z21 and (not z12 == z22):
		return mt(z12, z22)
	elif not z11 == z21 and z12 == z22:
		return mt(z11, z21)
	else:
		return 0

def virusIndices(p, v):
	strV = ''
	if len(p) < len(v):
		return 'No Match!'
	else:
		for i in range(len(p) - len(v) + 1):
			t = p[i:i + len(v)]
			fl = mt(t, v)
			if fl:
				strV += str(i) + ' '
		if len(strV) == 0:
			return 'No Match!'
		else:
			return strV.strip()
t = int(input())
for t_itr in range(t):
	pv = input().split()
	p = pv[0]
	v = pv[1]
	print(virusIndices(p, v))


import os
import sys

def small_match(w1, w2):
	counter = 0
	for i in range(len(w1)):
		if w1[i] != w2[i]:
			counter += 1
			if counter > 1:
				return 0
	return 1

def match(w1, w2):
	length = len(w1)
	if length < 10:
		return small_match(w1, w2)
	w11 = w1[:length // 2]
	w12 = w1[length // 2:]
	w21 = w2[:length // 2]
	w22 = w2[length // 2:]
	s1 = w11 == w21
	s2 = w12 == w22
	if s1 and s2:
		return 1
	elif s1 and (not s2):
		return match(w12, w22)
	elif not s1 and s2:
		return match(w11, w21)
	else:
		return 0

def virusIndices(p, v):
	res = ''
	if len(v) > len(p):
		return 'No Match!'
	else:
		for i in range(len(p) - len(v) + 1):
			temp = p[i:i + len(v)]
			flag = match(temp, v)
			if flag:
				res += str(i) + ' '
		if len(res) == 0:
			return 'No Match!'
		else:
			return res.strip()
t = int(input())
for t_itr in range(t):
	pv = input().split()
	p = pv[0]
	v = pv[1]
	print(virusIndices(p, v))


import os
import sys

def small_match(w1, w2):
	counter = 0
	for i in range(len(w1)):
		if w1[i] != w2[i]:
			counter += 1
			if counter > 1:
				return 0
	return 1

def match(w1, w2):
	length = len(w1)
	if length < 10:
		return small_match(w1, w2)
	w11 = w1[:length // 2]
	w12 = w1[length // 2:]
	w21 = w2[:length // 2]
	w22 = w2[length // 2:]
	s1 = w11 == w21
	s2 = w12 == w22
	if s1 and s2:
		return 1
	elif s1 and (not s2):
		return match(w12, w22)
	elif not s1 and s2:
		return match(w11, w21)
	else:
		return 0

def virusIndices(p, v):
	res = ''
	if len(v) > len(p):
		return 'No Match!'
	else:
		for i in range(len(p) - len(v) + 1):
			tmp = p[i:i + len(v)]
			flag = match(tmp, v)
			if flag:
				res += str(i) + ' '
		if len(res) == 0:
			return 'No Match!'
		else:
			return res.strip()
t = int(input())
for t_itr in range(t):
	pv = input().split()
	p = pv[0]
	v = pv[1]
	print(virusIndices(p, v))


import os
import sys

def small_match(w1, w2):
	counter = 0
	for i in range(len(w1)):
		if w1[i] != w2[i]:
			counter += 1
			if counter > 1:
				return 0
	return 1

def match(w1, w2):
	length = len(w1)
	if length < 10:
		return small_match(w1, w2)
	w11 = w1[:length // 2]
	w12 = w1[length // 2:]
	w21 = w2[:length // 2]
	w22 = w2[length // 2:]
	s1 = w11 == w21
	s2 = w12 == w22
	if s1 and s2:
		return 1
	elif s1 and (not s2):
		return match(w12, w22)
	elif not s1 and s2:
		return match(w11, w21)
	else:
		return 0

def virusIndices(p, v):
	res = ''
	if len(v) > len(p):
		return 'No Match!'
	else:
		for i in range(len(p) - len(v) + 1):
			temp = p[i:i + len(v)]
			flag = match(temp, v)
			if flag:
				res += str(i) + ' '
		if len(res) == 0:
			return 'No Match!'
		else:
			return res.strip()
t = int(input())
for t_itr in range(t):
	pv = input().split()
	p = pv[0]
	v = pv[1]
	print(virusIndices(p, v))


import os
import sys

def small_match(w1, w2):
	counter = 0
	for i in range(len(w1)):
		if w1[i] != w2[i]:
			counter += 1
			if counter > 1:
				return 0
	return 1

def match(w1, w2):
	length = len(w1)
	if length < 10:
		return small_match(w1, w2)
	w11 = w1[:length // 2]
	w12 = w1[length // 2:]
	w21 = w2[:length // 2]
	w22 = w2[length // 2:]
	s1 = w11 == w21
	s2 = w12 == w22
	if s1 and s2:
		return 1
	elif s1 and (not s2):
		return match(w12, w22)
	elif not s1 and s2:
		return match(w11, w21)
	else:
		return 0

def virusIndices(p, v):
	res = ''
	if len(v) > len(p):
		return 'No Match!'
	else:
		for i in range(len(p) - len(v) + 1):
			temp = p[i:i + len(v)]
			flag = match(temp, v)
			if flag:
				res += str(i) + ' '
		if len(res) == 0:
			return 'No Match!'
		else:
			return res.strip()
t = int(input())
for t_itr in range(t):
	pv = input().split()
	p = pv[0]
	v = pv[1]
	print(virusIndices(p, v))


import os
import sys

def binaryCompare(s1, s2):
	if len(s1) != len(s2):
		return 1
	if len(s1) == 1 and len(s2) == 1 and (s1 != s2):
		return 1
	if s1 == s2:
		return 0
	l = len(s1)
	mid = l // 2
	left_s1 = s1[:mid]
	left_s2 = s2[:mid]
	right_s1 = s1[mid:]
	right_s2 = s2[mid:]
	cmp_left = left_s1 != left_s2
	cmp_right = right_s1 != right_s2
	if cmp_left and cmp_right:
		return 2
	res = 0
	if cmp_left:
		res += binaryCompare(left_s1, left_s2)
	if cmp_right:
		res += binaryCompare(right_s1, right_s2)
	return res

def looseCompare(s1, s2):
	if len(s1) != len(s2):
		return 1
	if s1 == s2:
		return 0
	pos = 0
	diff = 0
	for i in range(len(s1)):
		if s1[i] != s2[i]:
			diff += 1
			if diff == 1:
				pos = i
		if diff > 1:
			skip = pos
			for j in range(1, pos // 2 + 1):
				aj = pos // 2 - j + 1
				if pos % aj == 0:
					if s1[:aj] * (pos // aj) == s1[:pos]:
						for k in range(1, pos // aj):
							if s1[:aj * k] != s2[:aj * k]:
								break
						skip = aj * (pos // aj - k)
						break
			return max(1, skip)
	return 0

def virusIndices(p, v):
	lp = len(p)
	lv = len(v)
	res = []
	i = 0
	while i < lp - lv + 1:
		comparison = binaryCompare(p[i:i + lv], v)
		if comparison < 2:
			res.append(i)
		i += 1
	if not res:
		print('No Match!')
	else:
		print(' '.join(map(str, res)))
t = int(input())
for t_itr in range(t):
	pv = input().split()
	p = pv[0]
	v = pv[1]
	virusIndices(p, v)


import os
import sys
from collections import Counter

def small_match(w1, w2):
	counter = 0
	for i in range(len(w1)):
		if w1[i] != w2[i]:
			counter += 1
			if counter > 1:
				return 0
	return 1

def match(w1, w2):
	length = len(w1)
	if length < 10:
		return small_match(w1, w2)
	w11 = w1[:length // 2]
	w12 = w1[length // 2:]
	w21 = w2[:length // 2]
	w22 = w2[length // 2:]
	s1 = w11 == w21
	s2 = w12 == w22
	if s1 and s2:
		return True
	elif s1 and (not s2):
		return match(w12, w22)
	elif not s1 and s2:
		return match(w11, w21)
	else:
		return 0

def virusIndices(p, v):
	res = ''
	if len(v) > len(p):
		return 'No Match!'
	else:
		for i in range(len(p) - len(v) + 1):
			temp = p[i:i + len(v)]
			flag = match(temp, v)
			if flag:
				res += str(i) + ' '
		if len(res) == 0:
			return 'No Match!'
		else:
			return res.strip()
t = int(input())
for t_itr in range(t):
	pv = input().split()
	p = pv[0]
	v = pv[1]
	print(virusIndices(p, v))


import os
import sys

def does_match(s1, s2, l):
	if l == 1 or s1 == s2:
		return True
	h = l // 2
	if s1[:h] == s2[:h]:
		return does_match(s1[h:], s2[h:], l - h)
	if s1[h:] == s2[h:]:
		return does_match(s1[:h], s2[:h], h)
	return False

def virusIndices(p, v):
	list = []
	for i in range(len(p) - len(v) + 1):
		if does_match(p[i:i + len(v)], v, len(v)):
			list.append(i)
	if list == []:
		print('No Match!')
	else:
		print(*list)
t = int(input())
for t_itr in range(t):
	pv = input().split()
	p = pv[0]
	v = pv[1]
	virusIndices(p, v)


import os
import sys

def small_match(s1, s2):
	counter = 0
	for i in range(len(s1)):
		if s1[i] != s2[i]:
			counter += 1
	if counter <= 1:
		return 1
	return 0

def match(s1, s2):
	length = len(s2)
	if length < 10:
		return small_match(s1, s2)
	s11 = s1[:length // 2]
	s12 = s1[length // 2:]
	s21 = s2[:length // 2]
	s22 = s2[length // 2:]
	v1 = s11 == s21
	v2 = s12 == s22
	if v1 and v2:
		return 1
	elif v1 and (not v2):
		return match(s12, s22)
	elif not v1 and v2:
		return match(s11, s21)
	else:
		return 0

def virusIndices(p, v):
	indices = ''
	if len(v) > len(p):
		print('No Match!', end='')
	else:
		for i in range(len(p) - len(v) + 1):
			to_check = p[i:i + len(v)]
			index = i
			if match(to_check, v) == 1:
				indices += str(index) + ' '
		if not indices:
			print('No Match!', end='')
		print(indices.strip())
t = int(input())
for t_itr in range(t):
	pv = input().split()
	p = pv[0]
	v = pv[1]
	virusIndices(p, v)


from collections import defaultdict
import re
_DEBUG = 0

def WM_approx_Ham1_search(pattern, text):
	m = len(pattern)
	S_table = defaultdict(int)
	for (i, c) in enumerate(pattern):
		S_table[c] |= 1 << i
	R0 = 0
	R1 = 0
	mask = 1 << m - 1
	for (j, c) in enumerate(text):
		S = S_table[c]
		shR0 = R0 << 1 | 1
		R0 = shR0 & S
		R1 = (R1 << 1 | 1) & S | shR0
		if _DEBUG:
			print('j= %2d msk=%s S=%s R0=%s R1=%s' % tuple([j] + map(bitstr, [mask, S, R0, R1])))
		if R0 & mask:
			yield (0, j - m + 1)
		elif R1 & mask:
			yield (1, j - m + 1)
if _DEBUG:

	def bitstr(num, mlen=8):
		wstr = ''
		for i in xrange(mlen):
			if num & 1:
				wstr = '1' + wstr
			else:
				wstr = '0' + wstr
			num >>= 1
		return wstr

def Ham_dist(s1, s2):
	assert len(s1) == len(s2)
	return sum((c1 != c2 for (c1, c2) in zip(s1, s2)))

def long_check(pattern, text):
	m = len(pattern)
	for i in xrange(len(text) - m + 1):
		d = Ham_dist(pattern, text[i:i + m])
		if d < 2:
			yield (d, i)

def Paul_McGuire_regex(pattern, text):
	searchSeqREStr = '(' + pattern + ')|(' + ')|('.join((pattern[:i] + '[a-z]'.replace(c, '') + pattern[i + 1:] for (i, c) in enumerate(pattern))) + ')'
	searchSeqRE = re.compile(searchSeqREStr)
	for match in searchSeqRE.finditer(text):
		locn = match.start()
		dist = int(bool(match.lastindex - 1))
		yield (dist, locn)
t = int(input())
for i in range(t):
	(p, v) = input().split()
	r = []
	for l in list(WM_approx_Ham1_search(v, p)):
		r.append(l[1])
	print(' '.join(map(str, r)) if r else 'No Match!')


import os
import sys

def match(pp, v):
	miss = 0
	length = len(pp)
	if length < 10:
		for i in range(len(v)):
			if pp[i] != v[i]:
				miss += 1
				if miss > 1:
					return 0
		return 1
	pp1 = pp[:length // 2]
	pp2 = pp[length // 2:]
	v1 = v[:length // 2]
	v2 = v[length // 2:]
	f = pp1 == v1
	l = pp2 == v2
	if f and l:
		return 1
	elif f and (not l):
		return match(pp2, v2)
	elif not f and l:
		return match(pp1, v1)
	else:
		return 0

def virusIndices(p, v):
	string = ''
	if len(v) > len(p):
		print('No Match!')
	else:
		for i in range(len(p) - len(v) + 1):
			flag = match(p[i:i + len(v)], v)
			if flag:
				string += str(i) + ' '
		if len(string) == 0:
			print('No Match!')
		else:
			print(string.rstrip())
t = int(input())
for t_itr in range(t):
	pv = input().split()
	p = pv[0]
	v = pv[1]
	virusIndices(p, v)


import os
import sys

def smallmatch(w1, w2):
	c = 0
	for i in range(len(w1)):
		if w1[i] != w2[i]:
			c += 1
			if c > 1:
				return 0
	return 1

def match(w1, w2):
	length = len(w1)
	if length < 10:
		return smallmatch(w1, w2)
	w11 = w1[:length // 2]
	w12 = w1[length // 2:]
	w21 = w2[:length // 2]
	w22 = w2[length // 2:]
	s1 = w11 == w21
	s2 = w12 == w22
	if s1 and s2:
		return 1
	elif s1 and (not s2):
		return match(w12, w22)
	elif not s1 and s2:
		return match(w11, w21)
	else:
		return 0

def virusIndices(p, v):
	res = ''
	if len(v) > len(p):
		return 'No Match!'
	else:
		for i in range(len(p) - len(v) + 1):
			temp = p[i:i + len(v)]
			flag = match(temp, v)
			if flag:
				res += str(i) + ' '
		if len(res) == 0:
			return 'No Match!'
		else:
			return res.strip()
t = int(input())
for t_itr in range(t):
	pv = input().split()
	p = pv[0]
	v = pv[1]
	print(virusIndices(p, v))


import os
import sys
import re

def small_match(w1, w2):
	counter = 0
	for i in range(len(w1)):
		if w1[i] != w2[i]:
			counter += 1
			if counter > 1:
				return 0
	return 1

def match(w1, w2):
	length = len(w1)
	if length < 10:
		return small_match(w1, w2)
	w11 = w1[:length // 2]
	w12 = w1[length // 2:]
	w21 = w2[:length // 2]
	w22 = w2[length // 2:]
	s1 = w11 == w21
	s2 = w12 == w22
	if s1 and s2:
		return 1
	elif s1 and (not s2):
		return match(w12, w22)
	elif not s1 and s2:
		return match(w11, w21)
	else:
		return 0

def virusIndices(p, v):
	res = ''
	if len(v) > len(p):
		return 'No Match!'
	else:
		for i in range(len(p) - len(v) + 1):
			temp = p[i:i + len(v)]
			flag = match(temp, v)
			if flag:
				res += str(i) + ' '
		if len(res) == 0:
			return 'No Match!'
		else:
			return res.strip()
t = int(input())
for t_itr in range(t):
	pv = input().split()
	p = pv[0]
	v = pv[1]
	print(virusIndices(p, v))


def similarity(st):
	rt = [len(st)]
	i = 1
	(f, fi) = (0, 0)
	k = 0
	while i < len(st):
		if fi < i < fi + f:
			if rt[i - fi] >= fi + f - i:
				k = fi + f - i
				(f, fi) = (0, 0)
			else:
				rt.append(rt[i - fi])
				i += 1
				k = 0
		else:
			while i + k < len(st) and st[k] == st[i + k]:
				k += 1
			rt.append(k)
			(f, fi) = (k, i)
			i += 1
			k = 0
	return rt

def similarityDiff(st, t):
	tmp = similarity(t)
	i = 0
	rt = []
	j = 0
	while i < len(st):
		while i + j < len(st) and j < len(t):
			if st[i + j] != t[j]:
				rt.append(j)
				break
			j += 1
		else:
			rt.append(j)
		if rt[i] > 1:
			for k in range(1, rt[i] - 1):
				if tmp[k] >= rt[i] - k:
					j = rt[i] - k
					i = i + k
					break
				else:
					rt.append(tmp[k])
			else:
				i = len(rt)
				j = 0
		else:
			i += 1
			j = 0
	return rt

def saveHuman(p, v):
	f = similarityDiff(p, v)
	l = similarityDiff(p[::-1], v[::-1])[::-1]
	rt = []
	for i in range(len(f)):
		if f[i] == len(v) or (i + len(v) - 1 < len(l) and f[i] + l[i + len(v) - 1] == len(v) - 1):
			rt.append(i)
	if len(rt) > 0:
		print(*rt, sep=' ')
	else:
		print('No Match!')
for t in range(int(input())):
	pv = input().strip().split()
	p = pv[0]
	v = pv[1]
	saveHuman(p, v)


from collections import Counter

def calc_words_diff(a, b):
	if a == b:
		return 0
	length = len(a)
	if length <= 16:
		r = 0
		for i in range(length):
			if a[i] != b[i]:
				r += 1
		return r
	x = length // 4
	case_1 = a[:x] != b[:x]
	case_2 = a[x:2 * x] != b[x:2 * x]
	case_3 = a[2 * x:3 * x] != b[2 * x:3 * x]
	case_4 = a[3 * x:] != b[3 * x:]
	if (case_1, case_2, case_3, case_4).count(True) > 1:
		return 2
	r = 0
	if case_1:
		r += calc_words_diff(a[:x], b[:x])
		if r > 1:
			return r
	if case_2:
		r += calc_words_diff(a[x:2 * x], b[x:2 * x])
		if r > 1:
			return r
	if case_3:
		r += calc_words_diff(a[2 * x:3 * x], b[2 * x:3 * x])
		if r > 1:
			return r
	if case_4:
		r += calc_words_diff(a[3 * x:], b[3 * x:])
	return r

def solution(p, v):
	result = []
	c = Counter(v)
	length_v = len(v)
	length_p = len(p)
	for i in range(length_v):
		if p[i] in c:
			c[p[i]] -= 1
	for i in range(length_p - length_v + 1):
		if len(c) == 1 and sum(c.values()) < 2:
			result.append(str(i))
			c[p[i]] += 1
			if i < length_p - length_v:
				c[p[i + length_v]] -= 1
			continue
		if any([i > 1 or i < -1 for i in c.values()]) or sum(c.values()) > 2:
			c[p[i]] += 1
			if i < length_p - length_v:
				c[p[i + length_v]] -= 1
			continue
		diff = calc_words_diff(p[i:i + length_v], v)
		if diff < 2:
			result.append(str(i))
		c[p[i]] += 1
		if i < length_p - length_v:
			c[p[i + length_v]] -= 1
	return print('No Match!') if not result else print(' '.join(result))
for _ in range(int(input())):
	solution(*input().split())


import os
import sys

def small_match(w1, w2):
	counter = 0
	for i in range(len(w1)):
		if w1[i] != w2[i]:
			counter += 1
			if counter > 1:
				return 0
	return 1

def match(w1, w2):
	length = len(w1)
	if length < 10:
		return small_match(w1, w2)
	w11 = w1[:length // 2]
	w12 = w1[length // 2:]
	w21 = w2[:length // 2]
	w22 = w2[length // 2:]
	s1 = w11 == w21
	s2 = w12 == w22
	if s1 and s2:
		return 1
	elif s1 and (not s2):
		return match(w12, w22)
	elif not s1 and s2:
		return match(w11, w21)
	else:
		return 0

def virusIndices(p, v):
	res = ''
	if len(v) > len(p):
		return 'NO MATCH'
	else:
		for i in range(len(p) - len(v) + 1):
			temp = p[i:i + len(v)]
			flag = match(temp, v)
			if flag:
				res += str(i) + ' '
		if len(res) == 0:
			return 'No Match!'
		else:
			return res.strip()
t = int(input())
for t_itr in range(t):
	pv = input().split()
	p = pv[0]
	v = pv[1]
	print(virusIndices(p, v))


import os
import sys

def small_match(w1, w2):
	counter = 0
	for i in range(len(w1)):
		if w1[i] != w2[i]:
			counter += 1
			if counter > 1:
				return 0
	return 1

def match(w1, w2):
	length = len(w1)
	if length < 10:
		return small_match(w1, w2)
	w11 = w1[:length // 2]
	w12 = w1[length // 2:]
	w21 = w2[:length // 2]
	w22 = w2[length // 2:]
	s1 = w11 == w21
	s2 = w12 == w22
	if s1 and s2:
		return 1
	elif s1 and (not s2):
		return match(w12, w22)
	elif not s1 and s2:
		return match(w11, w21)
	else:
		return 0

def virusIndices(p, v):
	res = ''
	if len(v) > len(p):
		return 'NO MATCH'
	else:
		for i in range(len(p) - len(v) + 1):
			temp = p[i:i + len(v)]
			flag = match(temp, v)
			if flag:
				res += str(i) + ' '
		if len(res) == 0:
			return 'No Match!'
		else:
			return res.strip()
t = int(input())
for t_itr in range(t):
	pv = input().split()
	p = pv[0]
	v = pv[1]
	print(virusIndices(p, v))


import os
import sys

def small_match(w1, w2):
	counter = 0
	for i in range(len(w1)):
		if w1[i] != w2[i]:
			counter += 1
			if counter > 1:
				return 0
	return 1

def match(w1, w2):
	length = len(w1)
	if length < 10:
		return small_match(w1, w2)
	w11 = w1[:length // 2]
	w12 = w1[length // 2:]
	w21 = w2[:length // 2]
	w22 = w2[length // 2:]
	s1 = w11 == w21
	s2 = w12 == w22
	if s1 and s2:
		return 1
	elif s1 and (not s2):
		return match(w12, w22)
	elif not s1 and s2:
		return match(w11, w21)
	else:
		return 0

def virusIndices(p, v):
	res = ''
	if len(v) > len(p):
		return 'NO MATCH'
	else:
		for i in range(len(p) - len(v) + 1):
			temp = p[i:i + len(v)]
			flag = match(temp, v)
			if flag:
				res += str(i) + ' '
		if len(res) == 0:
			return 'No Match!'
		else:
			return res.strip()
t = int(input())
for t_itr in range(t):
	pv = input().split()
	p = pv[0]
	v = pv[1]
	print(virusIndices(p, v))


import os
import sys

def small_match(w1, w2):
	counter = 0
	for i in range(len(w1)):
		if w1[i] != w2[i]:
			counter += 1
			if counter > 1:
				return 0
	return 1

def match(w1, w2):
	length = len(w1)
	if length < 10:
		return small_match(w1, w2)
	w11 = w1[:length // 2]
	w12 = w1[length // 2:]
	w21 = w2[:length // 2]
	w22 = w2[length // 2:]
	s1 = w11 == w21
	s2 = w12 == w22
	if s1 and s2:
		return 1
	elif s1 and (not s2):
		return match(w12, w22)
	elif not s1 and s2:
		return match(w11, w21)
	else:
		return 0

def virusIndices(p, v):
	res = ''
	if len(v) > len(p):
		return 'NO MATCH'
	else:
		for i in range(len(p) - len(v) + 1):
			temp = p[i:i + len(v)]
			flag = match(temp, v)
			if flag:
				res += str(i) + ' '
		if len(res) == 0:
			return 'No Match!'
		else:
			return res.strip()
t = int(input())
for t_itr in range(t):
	pv = input().split()
	p = pv[0]
	v = pv[1]
	print(virusIndices(p, v))


import os
import sys

def small_match(w1, w2):
	counter = 0
	for i in range(len(w1)):
		if w1[i] != w2[i]:
			counter += 1
			if counter > 1:
				return 0
	return 1

def match(w1, w2):
	length = len(w1)
	if length < 10:
		return small_match(w1, w2)
	w11 = w1[:length // 2]
	w12 = w1[length // 2:]
	w21 = w2[:length // 2]
	w22 = w2[length // 2:]
	s1 = w11 == w21
	s2 = w12 == w22
	if s1 and s2:
		return 1
	elif s1 and (not s2):
		return match(w12, w22)
	elif not s1 and s2:
		return match(w11, w21)
	else:
		return 0

def virusIndices(p, v):
	res = ''
	if len(v) > len(p):
		return 'NO MATCH'
	else:
		for i in range(len(p) - len(v) + 1):
			temp = p[i:i + len(v)]
			flag = match(temp, v)
			if flag:
				res += str(i) + ' '
		if len(res) == 0:
			return 'No Match!'
		else:
			return res.strip()
t = int(input())
for t_itr in range(t):
	pv = input().split()
	p = pv[0]
	v = pv[1]
	print(virusIndices(p, v))


import os
import sys

def small_match(w1, w2):
	counter = 0
	for i in range(len(w1)):
		if w1[i] != w2[i]:
			counter += 1
			if counter > 1:
				return 0
	return 1

def match(w1, w2):
	length = len(w1)
	if length < 10:
		return small_match(w1, w2)
	w11 = w1[:length // 2]
	w12 = w1[length // 2:]
	w21 = w2[:length // 2]
	w22 = w2[length // 2:]
	s1 = w11 == w21
	s2 = w12 == w22
	if s1 and s2:
		return 1
	elif s1 and (not s2):
		return match(w12, w22)
	elif not s1 and s2:
		return match(w11, w21)
	else:
		return 0

def virusIndices(p, v):
	res = ''
	if len(v) > len(p):
		return 'NO MATCH'
	else:
		for i in range(len(p) - len(v) + 1):
			temp = p[i:i + len(v)]
			flag = match(temp, v)
			if flag:
				res += str(i) + ' '
		if len(res) == 0:
			return 'No Match!'
		else:
			return res.strip()
t = int(input())
for t_itr in range(t):
	pv = input().split()
	p = pv[0]
	v = pv[1]
	print(virusIndices(p, v))


import os
import sys

def small_match(w1, w2):
	counter = 0
	for i in range(len(w1)):
		if w1[i] != w2[i]:
			counter += 1
			if counter > 1:
				return 0
	return 1

def match(w1, w2):
	length = len(w1)
	if length < 10:
		return small_match(w1, w2)
	w11 = w1[:length // 2]
	w12 = w1[length // 2:]
	w21 = w2[:length // 2]
	w22 = w2[length // 2:]
	s1 = w11 == w21
	s2 = w12 == w22
	if s1 and s2:
		return 1
	elif s1 and (not s2):
		return match(w12, w22)
	elif not s1 and s2:
		return match(w11, w21)
	else:
		return 0

def virusIndices(p, v):
	res = ''
	if len(v) > len(p):
		return 'No Match!'
	else:
		for i in range(len(p) - len(v) + 1):
			temp = p[i:i + len(v)]
			flag = match(temp, v)
			if flag:
				res += str(i) + ' '
		if len(res) == 0:
			return 'No Match!'
		else:
			return res.strip()
t = int(input())
for t_itr in range(t):
	pv = input().split()
	p = pv[0]
	v = pv[1]
	print(virusIndices(p, v))


import os
import sys

def small_match(w1, w2):
	counter = 0
	for i in range(len(w1)):
		if w1[i] != w2[i]:
			counter += 1
			if counter > 1:
				return 0
	return 1

def match(w1, w2):
	length = len(w1)
	if length < 10:
		return small_match(w1, w2)
	w11 = w1[:length // 2]
	w12 = w1[length // 2:]
	w21 = w2[:length // 2]
	w22 = w2[length // 2:]
	s1 = w11 == w21
	s2 = w12 == w22
	if s1 and s2:
		return 1
	elif s1 and (not s2):
		return match(w12, w22)
	elif not s1 and s2:
		return match(w11, w21)
	else:
		return 0

def virusIndices(p, v):
	res = ''
	if len(v) > len(p):
		return 'No Match!'
	else:
		for i in range(len(p) - len(v) + 1):
			temp = p[i:i + len(v)]
			flag = match(temp, v)
			if flag:
				res += str(i) + ' '
		if len(res) == 0:
			return 'No Match!'
		else:
			return res.strip()
t = int(input())
for t_itr in range(t):
	pv = input().split()
	p = pv[0]
	v = pv[1]
	print(virusIndices(p, v))


import math
import os
import random
import re
import sys

def small_match(w1, w2):
	counter = 0
	for i in range(len(w1)):
		if w1[i] != w2[i]:
			counter += 1
			if counter > 1:
				return 0
	return 1

def match(w1, w2):
	length = len(w1)
	if length < 10:
		return small_match(w1, w2)
	w11 = w1[:length // 2]
	w12 = w1[length // 2:]
	w21 = w2[:length // 2]
	w22 = w2[length // 2:]
	s1 = w11 == w21
	s2 = w12 == w22
	if s1 and s2:
		return 1
	elif s1 and (not s2):
		return match(w12, w22)
	elif not s1 and s2:
		return match(w11, w21)
	else:
		return 0

def virusIndices(p, v):
	res = ''
	if len(v) > len(p):
		return 'No Match!'
	else:
		for i in range(len(p) - len(v) + 1):
			temp = p[i:i + len(v)]
			flag = match(temp, v)
			if flag:
				res += str(i) + ' '
		if len(res) == 0:
			return 'No Match!'
		else:
			return res.strip()
t = int(input().strip())
for t_itr in range(t):
	first_multiple_input = input().rstrip().split()
	p = first_multiple_input[0]
	v = first_multiple_input[1]
	print(virusIndices(p, v))


import math
import os
import random
import re
import sys

def small_match(w1, w2):
	counter = 0
	for i in range(len(w1)):
		if w1[i] != w2[i]:
			counter += 1
			if counter > 1:
				return 0
	return 1

def match(w1, w2):
	length = len(w1)
	if length < 10:
		return small_match(w1, w2)
	w11 = w1[:length // 2]
	w12 = w1[length // 2:]
	w21 = w2[:length // 2]
	w22 = w2[length // 2:]
	s1 = w11 == w21
	s2 = w12 == w22
	if s1 and s2:
		return 1
	elif s1 and (not s2):
		return match(w12, w22)
	elif not s1 and s2:
		return match(w11, w21)
	else:
		return 0

def virusIndices(p, v):
	res = ''
	if len(v) > len(p):
		return 'No Match!'
	else:
		for i in range(len(p) - len(v) + 1):
			temp = p[i:i + len(v)]
			flag = match(temp, v)
			if flag:
				res += str(i) + ' '
		if len(res) == 0:
			return 'No Match!'
		else:
			return res.strip()
t = int(input().strip())
for t_itr in range(t):
	first_multiple_input = input().rstrip().split()
	p = first_multiple_input[0]
	v = first_multiple_input[1]
	print(virusIndices(p, v))


import os
import sys
import math
import re
from collections import defaultdict

def virusIndices(p, v):

	def WM_approx_Ham1_search(pattern, text):
		m = len(pattern)
		S_table = defaultdict(int)
		for (i, c) in enumerate(pattern):
			S_table[c] |= 1 << i
		R0 = 0
		R1 = 0
		mask = 1 << m - 1
		for (j, c) in enumerate(text):
			S = S_table[c]
			shR0 = R0 << 1 | 1
			R0 = shR0 & S
			R1 = (R1 << 1 | 1) & S | shR0
			if R0 & mask:
				yield (j - m + 1)
			elif R1 & mask:
				yield (j - m + 1)
	matches = list(WM_approx_Ham1_search(v, p))
	if not len(matches):
		print('No Match!')
	else:
		print(' '.join((str(ind) for ind in matches)))
t = int(input())
for t_itr in range(t):
	pv = input().split()
	p = pv[0]
	v = pv[1]
	virusIndices(p, v)


import os
import sys
import math
import re
from collections import defaultdict

def virusIndices(p, v):

	def WM_approx_Ham1_search(pattern, text):
		m = len(pattern)
		S_table = defaultdict(int)
		for (i, c) in enumerate(pattern):
			S_table[c] |= 1 << i
		R0 = 0
		R1 = 0
		mask = 1 << m - 1
		for (j, c) in enumerate(text):
			S = S_table[c]
			shR0 = R0 << 1 | 1
			R0 = shR0 & S
			R1 = (R1 << 1 | 1) & S | shR0
			if R0 & mask:
				yield (j - m + 1)
			elif R1 & mask:
				yield (j - m + 1)
	matches = list(WM_approx_Ham1_search(v, p))
	if not len(matches):
		print('No Match!')
	else:
		print(' '.join((str(ind) for ind in matches)))
t = int(input())
for t_itr in range(t):
	pv = input().split()
	p = pv[0]
	v = pv[1]
	virusIndices(p, v)


import math
import os
import os
import sys
import math
import re
from collections import defaultdict

def virusIndices(p, v):

	def WM_approx_Ham1_search(pattern, text):
		m = len(pattern)
		S_table = defaultdict(int)
		for (i, c) in enumerate(pattern):
			S_table[c] |= 1 << i
		R0 = 0
		R1 = 0
		mask = 1 << m - 1
		for (j, c) in enumerate(text):
			S = S_table[c]
			shR0 = R0 << 1 | 1
			R0 = shR0 & S
			R1 = (R1 << 1 | 1) & S | shR0
			if R0 & mask:
				yield (j - m + 1)
			elif R1 & mask:
				yield (j - m + 1)
	matches = list(WM_approx_Ham1_search(v, p))
	if not len(matches):
		print('No Match!')
	else:
		print(' '.join((str(ind) for ind in matches)))
t = int(input())
for t_itr in range(t):
	pv = input().split()
	p = pv[0]
	v = pv[1]
	virusIndices(p, v)


import os
import sys
import math
import re
from collections import defaultdict

def virusIndices(p, v):

	def WM_approx_Ham1_search(pattern, text):
		m = len(pattern)
		S_table = defaultdict(int)
		for (i, c) in enumerate(pattern):
			S_table[c] |= 1 << i
		R0 = 0
		R1 = 0
		mask = 1 << m - 1
		for (j, c) in enumerate(text):
			S = S_table[c]
			shR0 = R0 << 1 | 1
			R0 = shR0 & S
			R1 = (R1 << 1 | 1) & S | shR0
			if R0 & mask:
				yield (j - m + 1)
			elif R1 & mask:
				yield (j - m + 1)
	matches = list(WM_approx_Ham1_search(v, p))
	if not len(matches):
		print('No Match!')
	else:
		print(' '.join((str(ind) for ind in matches)))
t = int(input())
for t_itr in range(t):
	pv = input().split()
	p = pv[0]
	v = pv[1]
	virusIndices(p, v)


import os
import sys
import math
import re
from collections import defaultdict

def virusIndices(p, v):

	def WM_approx_Ham1_search(pattern, text):
		m = len(pattern)
		S_table = defaultdict(int)
		for (i, c) in enumerate(pattern):
			S_table[c] |= 1 << i
		R0 = 0
		R1 = 0
		mask = 1 << m - 1
		for (j, c) in enumerate(text):
			S = S_table[c]
			shR0 = R0 << 1 | 1
			R0 = shR0 & S
			R1 = (R1 << 1 | 1) & S | shR0
			if R0 & mask:
				yield (j - m + 1)
			elif R1 & mask:
				yield (j - m + 1)
	matches = list(WM_approx_Ham1_search(v, p))
	if not len(matches):
		print('No Match!')
	else:
		print(' '.join((str(ind) for ind in matches)))
t = int(input())
for t_itr in range(t):
	pv = input().split()
	p = pv[0]
	v = pv[1]
	virusIndices(p, v)


from collections import defaultdict
import re
_DEBUG = 0

def WM_approx_Ham1_search(pattern, text):
	m = len(pattern)
	S_table = defaultdict(int)
	for (i, c) in enumerate(pattern):
		S_table[c] |= 1 << i
	R0 = 0
	R1 = 0
	mask = 1 << m - 1
	for (j, c) in enumerate(text):
		S = S_table[c]
		shR0 = R0 << 1 | 1
		R0 = shR0 & S
		R1 = (R1 << 1 | 1) & S | shR0
		if _DEBUG:
			print('j= %2d msk=%s S=%s R0=%s R1=%s' % tuple([j] + map(bitstr, [mask, S, R0, R1])))
		if R0 & mask:
			yield (0, j - m + 1)
		elif R1 & mask:
			yield (1, j - m + 1)
if _DEBUG:

	def bitstr(num, mlen=8):
		wstr = ''
		for i in xrange(mlen):
			if num & 1:
				wstr = '1' + wstr
			else:
				wstr = '0' + wstr
			num >>= 1
		return wstr

def Ham_dist(s1, s2):
	assert len(s1) == len(s2)
	return sum((c1 != c2 for (c1, c2) in zip(s1, s2)))

def long_check(pattern, text):
	m = len(pattern)
	for i in xrange(len(text) - m + 1):
		d = Ham_dist(pattern, text[i:i + m])
		if d < 2:
			yield (d, i)

def Paul_McGuire_regex(pattern, text):
	searchSeqREStr = '(' + pattern + ')|(' + ')|('.join((pattern[:i] + '[a-z]'.replace(c, '') + pattern[i + 1:] for (i, c) in enumerate(pattern))) + ')'
	searchSeqRE = re.compile(searchSeqREStr)
	for match in searchSeqRE.finditer(text):
		locn = match.start()
		dist = int(bool(match.lastindex - 1))
		yield (dist, locn)
t = int(input())
for i in range(t):
	(p, v) = input().split()
	r = []
	for l in list(WM_approx_Ham1_search(v, p)):
		r.append(l[1])
	print(' '.join(map(str, r)) if r else 'No Match!')


class saveHuman:

	def printCheckDNA(self, dna, virus):
		lenVirus = len(virus)
		lenDna = len(dna)
		listVirusDna = []
		if lenVirus == 1:
			return ' '.join([str(i) for i in range(lenDna)])
		for i in range(lenDna - lenVirus + 1):
			subDna = dna[i:i + lenVirus]
			if subDna == virus or self.checkDNA(subDna, virus, lenVirus):
				listVirusDna.append(str(i))
		return ' '.join(listVirusDna) if len(listVirusDna) > 0 else 'No Match!'

	def checkDNA(self, dna, virus, lenVirus):
		if lenVirus == 1:
			return True
		subLen = int((lenVirus + 1) / 2)
		if dna[:subLen] == virus[:subLen]:
			return self.checkDNA(dna[subLen:], virus[subLen:], lenVirus - subLen)
		elif dna[subLen:] == virus[subLen:]:
			return self.checkDNA(dna[:subLen], virus[:subLen], subLen)
		else:
			return False
task = saveHuman()
for _ in range(int(input())):
	(dna, virus) = input().split()
	print(task.printCheckDNA(dna, virus))


import os
import sys
import math
import re
from collections import defaultdict

def virusIndices(p, v):

	def WM_approx_Ham1_search(pattern, text):
		m = len(pattern)
		S_table = defaultdict(int)
		for (i, c) in enumerate(pattern):
			S_table[c] |= 1 << i
		R0 = 0
		R1 = 0
		mask = 1 << m - 1
		for (j, c) in enumerate(text):
			S = S_table[c]
			shR0 = R0 << 1 | 1
			R0 = shR0 & S
			R1 = (R1 << 1 | 1) & S | shR0
			if R0 & mask:
				yield (j - m + 1)
			elif R1 & mask:
				yield (j - m + 1)
	matches = list(WM_approx_Ham1_search(v, p))
	if not len(matches):
		print('No Match!')
	else:
		print(' '.join((str(ind) for ind in matches)))
t = int(input())
for t_itr in range(t):
	pv = input().split()
	p = pv[0]
	v = pv[1]
	virusIndices(p, v)


import math
import os
import random
import re
import sys

def small_match(w1, w2):
	counter = 0
	for i in range(len(w1)):
		if w1[i] != w2[i]:
			counter += 1
			if counter > 1:
				return 0
	return 1

def match(w1, w2):
	length = len(w1)
	if length < 10:
		return small_match(w1, w2)
	w11 = w1[:length // 2]
	w12 = w1[length // 2:]
	w21 = w2[:length // 2]
	w22 = w2[length // 2:]
	s1 = w11 == w21
	s2 = w12 == w22
	if s1 and s2:
		return True
	elif s1 and (not s2):
		return match(w12, w22)
	elif not s1 and s2:
		return match(w11, w21)
	else:
		return False

def virusIndices(p, v):
	res = ''
	if len(v) > len(p):
		return 'No Match!'
	else:
		for i in range(len(p) - len(v) + 1):
			temp = p[i:i + len(v)]
			flag = match(temp, v)
			if flag:
				res += str(i) + ' '
		if len(res) == 0:
			return 'No Match!'
		else:
			return res.strip()
t = int(input().strip())
for t_itr in range(t):
	first_multiple_input = input().rstrip().split()
	p = first_multiple_input[0]
	v = first_multiple_input[1]
	print(virusIndices(p, v))


import os
import sys
import math
import re
from collections import defaultdict

def virusIndices(p, v):

	def WM_approx_Ham1_search(pattern, text):
		m = len(pattern)
		S_table = defaultdict(int)
		for (i, c) in enumerate(pattern):
			S_table[c] |= 1 << i
		R0 = 0
		R1 = 0
		mask = 1 << m - 1
		for (j, c) in enumerate(text):
			S = S_table[c]
			shR0 = R0 << 1 | 1
			R0 = shR0 & S
			R1 = (R1 << 1 | 1) & S | shR0
			if R0 & mask:
				yield (j - m + 1)
			elif R1 & mask:
				yield (j - m + 1)
	matches = list(WM_approx_Ham1_search(v, p))
	if not len(matches):
		print('No Match!')
	else:
		print(' '.join((str(ind) for ind in matches)))
t = int(input())
for t_itr in range(t):
	pv = input().split()
	p = pv[0]
	v = pv[1]
	virusIndices(p, v)


import math
import os
import random
import re
import sys

def virusIndices(p, v):

	def s_match(x, y):
		ct = 0
		for i in range(len(x)):
			if x[i] != y[i]:
				ct += 1
				if ct > 1:
					return 0
		return 1

	def match(x, y):
		if len(x) < 10:
			return s_match(x, y)
		x1 = x[:len(x) // 2]
		x2 = x[len(x) // 2:]
		y1 = y[:len(y) // 2]
		y2 = y[len(y) // 2:]
		s1 = x1 == y1
		s2 = x2 == y2
		if s1 and s2:
			return 1
		elif s1 and (not s2):
			return match(x2, y2)
		elif not s1 and s2:
			return match(x1, y1)
		else:
			return 0
	res = ''
	if len(v) > len(p):
		return 'No Match!'
	else:
		for i in range(len(p) - len(v) + 1):
			temp = p[i:i + len(v)]
			flag = match(temp, v)
			if flag:
				res += str(i) + ' '
		if len(res) == 0:
			return 'No Match!'
		else:
			return res.strip()
t = int(input().strip())
for t_itr in range(t):
	first_multiple_input = input().rstrip().split()
	p = first_multiple_input[0]
	v = first_multiple_input[1]
	print(virusIndices(p, v))


import os
import sys
import math
import re
from collections import defaultdict

def virusIndices(p, v):

	def WM_approx_Ham1_search(pattern, text):
		m = len(pattern)
		S_table = defaultdict(int)
		for (i, c) in enumerate(pattern):
			S_table[c] |= 1 << i
		R0 = 0
		R1 = 0
		mask = 1 << m - 1
		for (j, c) in enumerate(text):
			S = S_table[c]
			shR0 = R0 << 1 | 1
			R0 = shR0 & S
			R1 = (R1 << 1 | 1) & S | shR0
			if R0 & mask:
				yield (j - m + 1)
			elif R1 & mask:
				yield (j - m + 1)
	matches = list(WM_approx_Ham1_search(v, p))
	if not len(matches):
		print('No Match!')
	else:
		print(' '.join((str(ind) for ind in matches)))
t = int(input())
for t_itr in range(t):
	pv = input().split()
	p = pv[0]
	v = pv[1]
	virusIndices(p, v)


import os
import sys
import math
import re
from collections import defaultdict

def virusIndices(p, v):

	def WM_approx_Ham1_search(pattern, text):
		m = len(pattern)
		S_table = defaultdict(int)
		for (i, c) in enumerate(pattern):
			S_table[c] |= 1 << i
		R0 = 0
		R1 = 0
		mask = 1 << m - 1
		for (j, c) in enumerate(text):
			S = S_table[c]
			shR0 = R0 << 1 | 1
			R0 = shR0 & S
			R1 = (R1 << 1 | 1) & S | shR0
			if R0 & mask:
				yield (j - m + 1)
			elif R1 & mask:
				yield (j - m + 1)
	matches = list(WM_approx_Ham1_search(v, p))
	if not len(matches):
		print('No Match!')
	else:
		print(' '.join((str(ind) for ind in matches)))
t = int(input())
for t_itr in range(t):
	pv = input().split()
	p = pv[0]
	v = pv[1]
	virusIndices(p, v)


import os
import sys
import math
import re
from collections import defaultdict

def virusIndices(p, v):

	def WM_approx_Ham1_search(pattern, text):
		m = len(pattern)
		S_table = defaultdict(int)
		for (i, c) in enumerate(pattern):
			S_table[c] |= 1 << i
		R0 = 0
		R1 = 0
		mask = 1 << m - 1
		for (j, c) in enumerate(text):
			S = S_table[c]
			shR0 = R0 << 1 | 1
			R0 = shR0 & S
			R1 = (R1 << 1 | 1) & S | shR0
			if R0 & mask:
				yield (j - m + 1)
			elif R1 & mask:
				yield (j - m + 1)
	matches = list(WM_approx_Ham1_search(v, p))
	if not len(matches):
		print('No Match!')
	else:
		print(' '.join((str(ind) for ind in matches)))
t = int(input())
for t_itr in range(t):
	pv = input().split()
	p = pv[0]
	v = pv[1]
	virusIndices(p, v)


import os
import sys
import math
import re
from collections import defaultdict

def virusIndices(p, v):

	def WM_approx_Ham1_search(pattern, text):
		m = len(pattern)
		S_table = defaultdict(int)
		for (i, c) in enumerate(pattern):
			S_table[c] |= 1 << i
		R0 = 0
		R1 = 0
		mask = 1 << m - 1
		for (j, c) in enumerate(text):
			S = S_table[c]
			shR0 = R0 << 1 | 1
			R0 = shR0 & S
			R1 = (R1 << 1 | 1) & S | shR0
			if R0 & mask:
				yield (j - m + 1)
			elif R1 & mask:
				yield (j - m + 1)
	matches = list(WM_approx_Ham1_search(v, p))
	if not len(matches):
		print('No Match!')
	else:
		print(' '.join((str(ind) for ind in matches)))
t = int(input())
for t_itr in range(t):
	pv = input().split()
	p = pv[0]
	v = pv[1]
	virusIndices(p, v)


import os
import sys
import math
import re
from collections import defaultdict

def virusIndices(p, v):

	def WM_approx_Ham1_search(pattern, text):
		m = len(pattern)
		S_table = defaultdict(int)
		for (i, c) in enumerate(pattern):
			S_table[c] |= 1 << i
		R0 = 0
		R1 = 0
		mask = 1 << m - 1
		for (j, c) in enumerate(text):
			S = S_table[c]
			shR0 = R0 << 1 | 1
			R0 = shR0 & S
			R1 = (R1 << 1 | 1) & S | shR0
			if R0 & mask:
				yield (j - m + 1)
			elif R1 & mask:
				yield (j - m + 1)
	matches = list(WM_approx_Ham1_search(v, p))
	if not len(matches):
		print('No Match!')
	else:
		print(' '.join((str(ind) for ind in matches)))
t = int(input())
for t_itr in range(t):
	pv = input().split()
	p = pv[0]
	v = pv[1]
	virusIndices(p, v)


import os
import sys
import math
import re
from collections import defaultdict

def virusIndices(p, v):

	def WM_approx_Ham1_search(pattern, text):
		m = len(pattern)
		S_table = defaultdict(int)
		for (i, c) in enumerate(pattern):
			S_table[c] |= 1 << i
		R0 = 0
		R1 = 0
		mask = 1 << m - 1
		for (j, c) in enumerate(text):
			S = S_table[c]
			shR0 = R0 << 1 | 1
			R0 = shR0 & S
			R1 = (R1 << 1 | 1) & S | shR0
			if R0 & mask:
				yield (j - m + 1)
			elif R1 & mask:
				yield (j - m + 1)
	matches = list(WM_approx_Ham1_search(v, p))
	if not len(matches):
		print('No Match!')
	else:
		print(' '.join((str(ind) for ind in matches)))
t = int(input())
for t_itr in range(t):
	pv = input().split()
	p = pv[0]
	v = pv[1]
	virusIndices(p, v)


import os
import sys
import math
import re
from collections import defaultdict

def virusIndices(p, v):

	def WM_approx_Ham1_search(pattern, text):
		m = len(pattern)
		S_table = defaultdict(int)
		for (i, c) in enumerate(pattern):
			S_table[c] |= 1 << i
		R0 = 0
		R1 = 0
		mask = 1 << m - 1
		for (j, c) in enumerate(text):
			S = S_table[c]
			shR0 = R0 << 1 | 1
			R0 = shR0 & S
			R1 = (R1 << 1 | 1) & S | shR0
			if R0 & mask:
				yield (j - m + 1)
			elif R1 & mask:
				yield (j - m + 1)
	matches = list(WM_approx_Ham1_search(v, p))
	if not len(matches):
		print('No Match!')
	else:
		print(' '.join((str(ind) for ind in matches)))
t = int(input())
for t_itr in range(t):
	pv = input().split()
	p = pv[0]
	v = pv[1]
	virusIndices(p, v)


import math
import os
import random
import re
import sys
from collections import defaultdict

def virusIndices(p, v):

	def WM_approx_Ham1_search(pattern, text):
		m = len(pattern)
		S_table = defaultdict(int)
		for (i, c) in enumerate(pattern):
			S_table[c] |= 1 << i
		R0 = 0
		R1 = 0
		mask = 1 << m - 1
		for (j, c) in enumerate(text):
			S = S_table[c]
			shR0 = R0 << 1 | 1
			R0 = shR0 & S
			R1 = (R1 << 1 | 1) & S | shR0
			if R0 & mask:
				yield (j - m + 1)
			elif R1 & mask:
				yield (j - m + 1)
	matches = list(WM_approx_Ham1_search(v, p))
	if not len(matches):
		print('No Match!')
	else:
		print(' '.join((str(ind) for ind in matches)))
t = int(input().strip())
for t_itr in range(t):
	first_multiple_input = input().rstrip().split()
	p = first_multiple_input[0]
	v = first_multiple_input[1]
	virusIndices(p, v)


import math
import os
import random
import re
import sys

def match2(w1, w2):
	counter = 0
	for i in range(len(w1)):
		if w1[i] != w2[i]:
			counter += 1
		if counter > 1:
			return False
	return True

def match(w1, w2):
	length = len(w1)
	if len(w1) < 10:
		return match2(w1, w2)
	w11 = w1[:length // 2]
	w21 = w2[:length // 2]
	w12 = w1[length // 2:]
	w22 = w2[length // 2:]
	s1 = w11 == w21
	s2 = w12 == w22
	if s1 and s2:
		return True
	elif s1 and (not s2):
		return match(w12, w22)
	elif not s1 and s2:
		return match(w11, w21)
	else:
		return False

def virusIndices(p, v):
	res = []
	if len(v) > len(p):
		print('No Match!')
	else:
		for i in range(len(p) - len(v) + 1):
			temp = p[i:i + len(v)]
			flag = match(temp, v)
			if flag:
				res.append(str(i))
		if len(res) == 0:
			print('No Match!')
		else:
			print(' '.join(res))
t = int(input().strip())
for t_itr in range(t):
	first_multiple_input = input().rstrip().split()
	p = first_multiple_input[0]
	v = first_multiple_input[1]
	virusIndices(p, v)


import math
import os
import random
import re
import sys
from collections import defaultdict

def virusIndices(p, v):

	def WM_approx_Ham1_search(pattern, text):
		m = len(pattern)
		S_table = defaultdict(int)
		for (i, c) in enumerate(pattern):
			S_table[c] |= 1 << i
		R0 = 0
		R1 = 0
		mask = 1 << m - 1
		for (j, c) in enumerate(text):
			S = S_table[c]
			shR0 = R0 << 1 | 1
			R0 = shR0 & S
			R1 = (R1 << 1 | 1) & S | shR0
			if R0 & mask:
				yield (j - m + 1)
			elif R1 & mask:
				yield (j - m + 1)
	matches = list(WM_approx_Ham1_search(v, p))
	if not len(matches):
		print('No Match!')
	else:
		print(' '.join((str(ind) for ind in matches)))
t = int(input())
for t_itr in range(t):
	pv = input().split()
	p = pv[0]
	v = pv[1]
	virusIndices(p, v)


import os
import sys
import math
import re
from collections import defaultdict

def virusIndices(p, v):

	def WM_approx_Ham1_search(pattern, text):
		m = len(pattern)
		S_table = defaultdict(int)
		for (i, c) in enumerate(pattern):
			S_table[c] |= 1 << i
		R0 = 0
		R1 = 0
		mask = 1 << m - 1
		for (j, c) in enumerate(text):
			S = S_table[c]
			shR0 = R0 << 1 | 1
			R0 = shR0 & S
			R1 = (R1 << 1 | 1) & S | shR0
			if R0 & mask:
				yield (j - m + 1)
			elif R1 & mask:
				yield (j - m + 1)
	matches = list(WM_approx_Ham1_search(v, p))
	if not len(matches):
		print('No Match!')
	else:
		print(' '.join((str(ind) for ind in matches)))
t = int(input())
for t_itr in range(t):
	pv = input().split()
	p = pv[0]
	v = pv[1]
	virusIndices(p, v)


import math
import os
import random
import re
import sys

def small_match(w1, w2):
	counter = 0
	for i in range(len(w1)):
		if w1[i] != w2[i]:
			counter += 1
			if counter > 1:
				return 0
	return 1

def match(w1, w2):
	length = len(w1)
	if length < 10:
		return small_match(w1, w2)
	w11 = w1[:length // 2]
	w12 = w1[length // 2:]
	w21 = w2[:length // 2]
	w22 = w2[length // 2:]
	s1 = w11 == w21
	s2 = w12 == w22
	if s1 and s2:
		return True
	elif s1 and (not s2):
		return match(w12, w22)
	elif not s1 and s2:
		return match(w11, w21)
	else:
		return False

def virusIndices(p, v):
	res = ''
	if len(v) > len(p):
		return 'No Match!'
	else:
		for i in range(len(p) - len(v) + 1):
			temp = p[i:i + len(v)]
			flag = match(temp, v)
			if flag:
				res += str(i) + ' '
		if len(res) == 0:
			return 'No Match!'
		else:
			return res.strip()
t = int(input().strip())
for t_itr in range(t):
	first_multiple_input = input().rstrip().split()
	p = first_multiple_input[0]
	v = first_multiple_input[1]
	print(virusIndices(p, v))


import os
import sys
import math
import re
from collections import defaultdict

def virusIndices(p, v):

	def WM_approx_Ham1_search(pattern, text):
		m = len(pattern)
		S_table = defaultdict(int)
		for (i, c) in enumerate(pattern):
			S_table[c] |= 1 << i
		R0 = 0
		R1 = 0
		mask = 1 << m - 1
		for (j, c) in enumerate(text):
			S = S_table[c]
			shR0 = R0 << 1 | 1
			R0 = shR0 & S
			R1 = (R1 << 1 | 1) & S | shR0
			if R0 & mask:
				yield (j - m + 1)
			elif R1 & mask:
				yield (j - m + 1)
	matches = list(WM_approx_Ham1_search(v, p))
	if not len(matches):
		print('No Match!')
	else:
		print(' '.join((str(ind) for ind in matches)))
t = int(input())
for t_itr in range(t):
	pv = input().split()
	p = pv[0]
	v = pv[1]
	virusIndices(p, v)