题目描述

马上就要复赛了！

徐老师决定在赛前重新整理一下自己买的各种学习用书、真题解析、游戏攻略（好像混进来了什么奇怪的东西）

为了方便描述

• 学习用书使用数字 $1 \sim 9$ 表示，其中数字越大表示重要程度越高
• 真题解析使用小写字母 $a \sim z$ 表示，其中字母越靠后表示重要程度越高
• 游戏攻略使用大写字母 $A \sim Z$ 表示，其中字母越靠后表示重要程度越高

这些书被徐老师堆在一个书架上，徐老师希望把这些书分门别类的放好，并且每种书都分别按照 重要程度 依次摆放，这样他就可以快速的查阅到自己需要的内容了

也就是说徐老师希望：同一类的书被放在一起，并且这类书按照重要程度依次摆放

但是由于徐老师放的书实在是太多了，导致没有办法把书全部拿出来重新摆放，他每次只能抽出其中的一本书，将这本书放到书架的最前面或者书架的最后面

例如现在书架上的书排列情况是：$abc3ABC12$，那么徐老师可以抽出 $3$ 这本书，将它放到书架最后，变成 $abcABC123$

徐老师想知道他最少需要操作几次书才能整理完书架？

P.S. 三类书可以以任意顺序摆放，例如可以学习用书在前，也可以真题解析在前，也可以游戏攻略在前，徐老师对类别顺序不作要求

输入格式

本题包含多组测试数据

输入第一行包含一个整数 $T$ 表示测试数据数量

对于每组测试数据输入一行包含一个字符串 $S$ 表示当前书架上书的摆放情况，含义如题

输出格式

对于每组测试数据输出一个整数表示徐老师最小的操作次数

数据范围

对于 $30\%$ 的数据，$1 \leq T \leq 10$，$|S| \leq 5，\sum{|S|} \leq 50$。

对于 $60\%$ 的数据，$1 \leq T \leq 10^3$，$|S| \leq 10^4，\sum{|S|} \leq 3 * 10^4$。

对于 $100\%$ 的数据，$1 \leq T \leq 10^5$，$|S| \leq 10^6，\sum{|S|} \leq 3 * 10^6$。

样例输入

6
Aa12324
12213
Aa12213
abc3ABC12
BBCaaAa8bc37
1QHWUFBABLFJQ2

样例输出

2
1
3
1
2
11