Migrated from Lutece 161 大小写切换

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

小明虽然还没有上学，可妈妈很早就教了他很多东西了，数数，认字还有写英文字母他都会了！五岁生日那天妈妈告诉小明他可以玩家里的大电脑了，不过只能用来打字。小明知道，只要学会了打字，他就可以跟表姐一样用电脑跟外国人说话聊天了，这样还能跟科学家舅舅说话呢，所以小明很勤奋的熟悉着键盘，一个键一个键的问妈妈那是做什么的。

一个月后，小明可以看着那个接在电脑上的“电视”然后按照顺序打出“电视”上画出的英文字母了。小明的手不够大，所以按键盘上的键会很慢也很累。更让人讨厌的就是还要切换大小写！！！妈妈说键盘刚开始的时候是小写模式，这个时候打出来的字母是小写的，可是如果要打出大写字母的话就要换模式，方法就是按一下键盘上的CapsLock键，这样就可以打出大写的字母了。同样，在大写模式的时候按下CapsLock键就可以重新回到小写模式。

妈妈还说，如果不想换模式的话，还可以用shift键来改模式打字符，不过shift必须要和字母键同时按下去，这样就可以在小写模式下打大写字母、大写模式下打小写字母了。当然，放开了shift，打出的还是当前这个模式的字母。

每天妈妈都给了小明一些打字任务，小明只要在电脑上按照顺序打完这些字母就可以得到零花钱。对小明来说，用自己的小手按键盘是一件很累的事情，所以小明每打一个字母就会松开手指休息一下。为了最快的完成妈妈给定的打字任务，小明想知道他最少要按多少个键才能完成，你帮帮他吧！

Input

输入的第一行是$T$（不超过$100$）。$T$表示测试部分的个数，每一部分都要求单独计算并按照要求输出结果。每组数据为一行字符，其中只有大写和小写字母，每组数据的字符数不超过$200$。

Output

对于每个测试部分，请输出每个问题的正确答案。每组数据输出一行，并且只有一个整数，表示打完字符串所需的最少按键次数。

Samples

4
AAAAAA
aaaaaa
aaaAAA
AAAaaa

7
6
7
8

Resources

zhilu