圣诞节就要到了，为了答谢新老客户的厚爱，位于普罗旺斯的Snow & Leaf咖啡屋给北航的师生邮寄来一个巨大圣诞树，上面挂满了各种各样的礼物。不同于别的圣诞树的是，上面的礼物都是一对一对的，每一对相同礼物都是用一根缘分之绳连起来的，而且对与对之间不重复。更令人兴奋的是，它长得还是特别像二叉树。

礼物人人都想拿，所以报名的人太多了。由于大家都是程序设计的高手，Snow & Leaf的老板娘就说，我当初准备缘分之绳花了很久的时间，如果你们能算出总共有多长，就可以在上面挑选一个礼物，并和选择了对应礼物的人，一起免费普罗旺斯一周游。

二叉树用广义表给出，礼物节点用’A’-‘Z’的字母表示，保证节点有偶数个，缘分之绳都沿着二叉树的边，每一个父子之间边长为1。

输入第一行为整数n，表示数据的组数。接下来的n行，每行一个字符串a，是用广义表表示的二叉树。

输出有n行，每行一个整数length，表示缘分之绳的总长度。-Christmas is coming, to thank the love of old and new customers located in the Snow & Leaf Cafe Provence to Northern students and teachers

Mail to a huge Christmas tree, hung above a variety of gifts. Unlike other Christmas tree is a gift above all

Is a one to one right, each pair of the same gifts are connected with a fate of the rope together, but not between right and on repeat. Even more

Exciting, it looks like a binary tree or as a special.

Everyone went to get a gift, so too many people signed up. Because we are a master of programming, Snow & Leaf s boss

Say, the fate of the rope I had prepared for a long time to spend, and if you can figure out how long in total, to be selected in the above

A gift, and gifts, and select the corresponding person, one week with free tour of Provence.

Generalized table shows the binary tree, gifts node with　A - Z　the letter said, to ensure that there is an even number of nodes, along all the strings of fate

The binary tree edges,