E. Смешные подстроки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Поликарп придумал новый язык программирования. В нем есть только два типа команд:

  1. «x := s» — назначить переменной с именем x значение s (где s - строка). Например, команда var := hello присваивает переменной с именем var значение hello. Обратите внимание, что s - это значение строки, а не имя переменной. Между названием переменной, оператором := и строкой находится ровно по одному пробелу.
  2. «x = a + b» — назначить переменной с именем x конкатенацию двух переменных a и b. Например, если программа состоит из трех команд a := hello, b := world, c = a + b, то переменная c будет содержать строку helloworld. Гарантируется, что программа корректна и переменные a и b были определены ранее. Между названиями переменных и операторами = и + находится ровно по одному пробелу.

Все имена переменных и строки состоят только из строчных букв английского алфавита и состоят не больше, чем из $$$5$$$ символов.

Результатом работы программы является количество вхождений строки haha в строке, которая была записана в переменную в последней команде.

Поликарп очень устал, изобретая этот язык. Он просит вас реализовать его. Ваша задача состоит в том, чтобы — для заданных программных операторов вычислить количество вхождений строки haha в последней назначенной переменной.

Входные данные

В первой строке находится целое число $$$t$$$ ($$$1 \le t \le 10^3$$$). Далее следуют $$$t$$$ наборов входных данных.

В первой строке каждого набора входных данных находятся одно целое число $$$n$$$ — ($$$1 \le n \le 50$$$) — количество команд в программе. Все имена переменных и строки гарантированно состоят только из строчных букв английского алфавита и состоят не больше, чем из $$$5$$$ символов.

Далее следуют $$$n$$$ строк описывающих команды в формате из условия выше. Гарантируется, что программа корректна.

Выходные данные

Для каждого набора входных данных выведите количество вхождений подстроки haha в строку, которая была записана в переменную в последней команде.

Пример
Входные данные
4
6
a := h
b := aha
c = a + b
c = c + c
e = c + c
d = a + c
15
x := haha
x = x + x
x = x + x
x = x + x
x = x + x
x = x + x
x = x + x
x = x + x
x = x + x
x = x + x
x = x + x
x = x + x
x = x + x
x = x + x
x = x + x
1
haha := hah
5
haahh := aaaha
ahhhh = haahh + haahh
haahh = haahh + haahh
ahhhh = ahhhh + haahh
ahhaa = haahh + ahhhh
Выходные данные
3
32767
0
0
Примечание

В первом наборе входных данных результат — значение переменной d=hhahahaha.