A. Harker!!
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Given $$$n$$$ strings $$$s_1, \dots, s_n$$$, output whether or not each string contains a substring "harker".

Input

The first line contains the value of $$$n$$$. The next $$$n$$$ lines contain the strings $$$s_1, \dots, s_n$$$.

It is guaranteed that $$$n\geq 1$$$, each string has a length of at least one, and the sum of the lengths of the strings is at most $$$10^5$$$.

Each string only consists of lowercase letters from the Latin alphabet.

Output

Output $$$n$$$ lines. The $$$i$$$-th line contains 1 if the string contains "harker" as a substring; else, output 0.

Example
Input
4
abcd
harkerharker
aharker
datar
Output
0
1
1
0