• 你那篇自传写得怎么样了？
• 呃，Ania，什么？波兰语课有作业吗？
• 拜托，我们本来应该写一篇自传的。你忘了吗？
• 我忘了。我能抄你的吗？
• 你想抄一篇自传！？好吧，但至少要做些修改。

给定一个由小写英文字母组成的字符串 $s$。这是 Ania 写的一篇自传，这意味着它可能包含单词 ania 作为连续子串，甚至可能出现多次。确定需要修改 $s$ 中的最少字符数，使得它不包含 ania 作为连续子串。

输入格式

第一行包含测试用例的数量 $z$ ($1 \le z \le 10\,000$)。接下来是各测试用例的描述。

每个测试用例仅包含一行，即字符串 $s$ —— Ania 的自传。字符串长度为 $l$ ($1 \le l \le 10^6$)。它仅由小写英文字母组成。

所有测试用例的字符串总长度不超过 $5\,000\,000$。

输出格式

对于每个测试用例，在单独的一行中输出一个整数，表示为了使自传不包含子串 ania 而必须进行的最少修改次数。

样例

样例输入 1

3
aniasieurodzilaapotemnicsieniedzialo
nicciekawegouanianiagnieszkianialicji
jeszczekrotszaautobiografiaani

样例输出 1

1
2
0