import re import itertools def prepare(): rememo = [] words_original = [c for c in 'goodproblem'] for i in range(12): for pos in itertools.combinations(range(11), i): words = words_original[:] for p in pos: words[p] = '.' pattern = ''.join(words[:4] + ['.*'] + words[4:]) compiled = re.compile(pattern) rememo.append(i, compiled) return rememo def solve(S, rememo): for i, compiled in rememo: result = compiled.search(S) if result: return i if __name__ == '__main__': rememo = prepare() T = int(input()) for t in range(T): print(solve(input(), rememo))