HIIT remains

import sys
def asints(s):
	return [int(x.strip()) for x in s.split()]
def asoneint(s):
	return int(s.strip())
lines = sys.stdin.readlines()

target = "HIIT"

t = asoneint(lines[0])
for i in range(t):
	s = lines[i+1]
	arr = [[0 for y in range(len(target))] for x in range(len(s))]
	for i,a in enumerate(s):
		for j in range(len(target)):
			arr[i][j] = arr[i-1][j]
		for j in range(len(target)):
			if a == target[j]:
				if j == 0:
					arr[i][j] += 1
				else:
					arr[i][j] += arr[i-1][j-1]
	from pprint import pprint
	print arr[-1][-1]

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: TIME LIMIT EXCEEDED

Test 4

Verdict: ACCEPTED