Background

无

Description

十七去参加了ICPC国际大学生程序设计竞赛(想想就好)，他非常喜欢比赛时的气球。

在ICPC国际大学生程序设计竞赛中，当一只队伍正确提交一道题目，就会在队伍旁边升起一只代表该题的气球，如果某只队伍是第一个解决该题的队伍，则会额外升起一只“FIRST PROBLEM SOLVED”的气球。 现在给你在场队伍正确提交题目的顺序，请你求出场上会升起多少只气球

Format

Input

第一行为一个整数 T(1≤T≤100)，代表测试用例的数量。

接下来T行，每行一个只含大写字母的字符s(1≤s.length()≤100) 就是长度的大小，为在场队伍正确提交题目的顺序。

Output

对于每个测试用例输出一行，为一个正整数，表示场上会升起的气球的数量。

Samples

5
ABA
A
ORZ
BAAAA
BKPT

5
2
6
7
8

Limitation

1s, 256mb for each test case.