今天是 XIIX 的生日。XIIX 想和他的好朋友去烧烤。他们去超市买了很多食物，然后骑车前往老鹰嘴，那是一个适合户外烧烤的好地方。

XIIX 认为一个完美的烧烤字符串必须满足 $abba$ 的格式（就像他的名字一样）。也就是说，一个完美的烧烤字符串满足 $s_i = s_{i+3}$，$s_{i+1} = s_{i+2}$（其中 $i \equiv 1 \pmod 4$），且长度 $len \equiv 0 \pmod 4$，下标从 $1$ 开始。注意，空字符串也是一个完美的字符串。

然而，XIIX 太忙了，没时间准备烧烤字符串。它可能不是一个完美的字符串。现在你可以在 $1$ 个单位时间内修改、添加或删除一个字母。你能否在最短的时间内将烧烤字符串转换为一个完美的字符串？

输入格式

每个测试包含多个测试用例。第一行包含测试用例的数量 $T$ ($1 \le T \le 12$)。 接下来是各测试用例的描述。 每个测试用例仅包含一个字符串，代表烧烤字符串。保证字符串的长度不超过 $10^6$。字符串中的所有字母均为小写。

输出格式

对于每个测试用例： 输出一行一个整数，表示最少需要的单位时间。

样例

输入格式 1

1
abbba

输出格式 1

1