시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 256 MB158442925.893%

문제

알파벳 대문자로만 이루어진 문자열 S가 있고, 길이는 N이다. S[i]는 S의 i번째 문자를 나타내고, S[i:j]는 S[i], S[i+1], ..., S[j-1], S[j]에 해당하는 S의 부분 문자열을 나타낸다. 이 문제에서 사용하는 문자열의 인덱스는 1부터 시작한다.

U(i, j)는 S[i:j]에 나타나는 알파벳을 순서대로 정렬한 문자열을 의미하고, 중복해서 나타나는 알파벳은 제외한다.

예를 들어, S = "ABCBA" 인 경우 U(1, 3) = "ABC"가 되며, U(2, 4) = "BC", U(1, 5) = "ABC"이다. 

모든 1 ≤ i ≤ j ≤ N에 대하여 U(i, j)을 구했을 때 이 문자열 중에서 서로 다른 문자열이 모두 몇 개 있는지 구해보자.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 문자열 S가 주어진다.

출력

각 테스트 케이스에 대해서 U(i, j)에 서로 다른 문자열이 몇 개 있는지 출력한다.

제한

  • 1 ≤ T ≤ 10
  • 1 ≤ N ≤ 100,000

예제 입력 1

4
AAA
ABCBA
ABABAB
ABCXYZABC

예제 출력 1

1
6
3
30

힌트

두 번째 예제의 경우 A, B, C, AB, BC, ABC 총 여섯 개의 문자열이 존재한다.

세 번째 예제의 경우 A, B, AB 총 세 개의 문자열이 존재한다.

W3sicHJvYmxlbV9pZCI6IjE3NDY0IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjNTRjXHVkMzBjXHViY2IzIFx1YmIzOFx1Yzc5MFx1YzVmNCIsImRlc2NyaXB0aW9uIjoiPHA+XHVjNTRjXHVkMzBjXHViY2IzIFx1YjMwMFx1YmIzOFx1Yzc5MFx1Yjg1Y1x1YjljYyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHViYjM4XHVjNzkwXHVjNWY0IFNcdWFjMDAgXHVjNzg4XHVhY2UwLCBcdWFlMzhcdWM3NzRcdWIyOTQgTlx1Yzc3NFx1YjJlNC4gU1tpXVx1YjI5NCBTXHVjNzU4IGlcdWJjODhcdWM5ZjggXHViYjM4XHVjNzkwXHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YWNlMCwgU1tpOmpdXHViMjk0Jm5ic3A7U1tpXSwgU1tpKzFdLCAuLi4sIFNbai0xXSwgU1tqXVx1YzVkMCBcdWQ1NzRcdWIyZjlcdWQ1NThcdWIyOTQgU1x1Yzc1OCBcdWJkODBcdWJkODQgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzQ0IFx1YjA5OFx1ZDBjMFx1YjBiOFx1YjJlNC4gXHVjNzc0IFx1YmIzOFx1YzgxY1x1YzVkMFx1YzExYyBcdWMwYWNcdWM2YTlcdWQ1NThcdWIyOTQgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzU4IFx1Yzc3OFx1YjM3MVx1YzJhNFx1YjI5NCAxXHViZDgwXHVkMTMwIFx1YzJkY1x1Yzc5MVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+VShpLCBqKVx1YjI5NCBTW2k6al1cdWM1ZDAgXHViMDk4XHVkMGMwXHViMDk4XHViMjk0IFx1YzU0Y1x1ZDMwY1x1YmNiM1x1Yzc0NCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVjODE1XHViODJjXHVkNTVjIFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc0NCBcdWM3NThcdWJiZjhcdWQ1NThcdWFjZTAsIFx1YzkxMVx1YmNmNVx1ZDU3NFx1YzExYyBcdWIwOThcdWQwYzBcdWIwOThcdWIyOTQgXHVjNTRjXHVkMzBjXHViY2IzXHVjNzQwIFx1YzgxY1x1YzY3OFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgUyA9ICZxdW90O0FCQ0JBJnF1b3Q7IFx1Yzc3OCBcdWFjYmRcdWM2YjAgVSgxLCAzKSA9ICZxdW90O0FCQyZxdW90O1x1YWMwMCBcdWI0MThcdWJhNzAsIFUoMiwgNCkgPSAmcXVvdDtCQyZxdW90OywgVSgxLCA1KSA9ICZxdW90O0FCQyZxdW90O1x1Yzc3NFx1YjJlNC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+XHViYWE4XHViNGUwIDEgJmxlOyBpICZsZTsgaiAmbGU7IE5cdWM1ZDAgXHViMzAwXHVkNTU4XHVjNWVjJm5ic3A7VShpLCBqKVx1Yzc0NCBcdWFkNmNcdWQ1ODhcdWM3NDQgXHViNTRjIFx1Yzc3NCBcdWJiMzhcdWM3OTBcdWM1ZjQmbmJzcDtcdWM5MTFcdWM1ZDBcdWMxMWMgXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3OCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NzQgXHViYWE4XHViNDUwIFx1YmE4NyBcdWFjMWMgXHVjNzg4XHViMjk0XHVjOWMwIFx1YWQ2Y1x1ZDU3NFx1YmNmNFx1Yzc5MC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWFjMWNcdWMyMTggVFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IFx1ZDU1YyBcdWM5MDRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YWNlMCwgXHViYjM4XHVjNzkwXHVjNWY0IFNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYyBVKGksIGopXHVjNWQwJm5ic3A7XHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3OCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NzQgXHViYTg3IFx1YWMxYyBcdWM3ODhcdWIyOTRcdWM5YzAgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8cD5cdWI0NTAgXHViYzg4XHVjOWY4IFx1YzYwOFx1YzgxY1x1Yzc1OCBcdWFjYmRcdWM2YjAgQSwgQiwgQywgQUIsIEJDLCBBQkMgXHVjZDFkIFx1YzVlY1x1YzEyZiBcdWFjMWNcdWM3NTggXHViYjM4XHVjNzkwXHVjNWY0XHVjNzc0IFx1Yzg3NFx1YzdhY1x1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMTM4IFx1YmM4OFx1YzlmOCBcdWM2MDhcdWM4MWNcdWM3NTggXHVhY2JkXHVjNmIwIEEsIEIsIEFCIFx1Y2QxZCBcdWMxMzggXHVhYzFjXHVjNzU4IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NCBcdWM4NzRcdWM3YWNcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4iLCJsaW1pdCI6Ijx1bD5cclxuXHQ8bGk+MSAmbGU7IFQgJmxlOyAxMDxcL2xpPlxyXG5cdDxsaT4xICZsZTsgTiAmbGU7IDEwMCwwMDA8XC9saT5cclxuPFwvdWw+XHJcbiJ9LHsicHJvYmxlbV9pZCI6IjE3NDY0IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQWxwaGFiZXQgU3RyaW5nIiwiZGVzY3JpcHRpb24iOiI8cD5Db25zaWRlciBhIHN0cmluZyBTIG9mIGxlbmd0aCBOJm5ic3A7dGhhdCBjb25zaXN0cyBvbmx5IG9mIHVwcGVyY2FzZSBFbmdsaXNoIGFscGhhYmV0cy48XC9wPlxyXG5cclxuPHA+U1tpXSByZXByZXNlbnRzIHRoZSBpLXRoIGNoYXJhY3RlciBvZiBTLCBhbmQgU1tpOmpdIGlzIHRoZSBzdWJzdHJpbmcgb2YgUywgU1tpXSwgU1tpKzFdLCAuLi4sIFNbai0xXSwgU1tqXSAoaW4gdGhpcyBwcm9ibGVtIHdlIHVzZSAxLWJhc2VkIGluZGV4KS48XC9wPlxyXG5cclxuPHA+VShpLCBqKSBpcyB0aGUgc29ydGVkIHN0cmluZyBvZiB1bmlxdWUgY2hhcmFjdGVycyAoYWxwaGFiZXRzKSB0aGF0IGFwcGVhciBpbiBTW2k6al0uPFwvcD5cclxuXHJcbjxwPkZvciBpbnN0YW5jZSwgaWYgUyA9ICZxdW90O0FCQ0JBJnF1b3Q7LCB3ZSB3b3VsZCBoYXZlIFUoMSwgMykgPSAmcXVvdDtBQkMmcXVvdDssIFUoMiwgNCkgPSAmcXVvdDtCQyZxdW90OywgYW5kIFUoMSwgNSkgPSAmcXVvdDtBQkMmcXVvdDsuPFwvcD5cclxuXHJcbjxwPldlIHdhbnQgdG8ga25vdyB0aGUgbnVtYmVyIG9mIHVuaXF1ZSBzdGluZ3MgYWNyb3NzIGFsbCBVKGksIGopIHdpdGggMSAmbGU7IGkgJmxlOyBqICZsZTsgTi48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIHdpbGwgY29udGFpbiBvbmUgaW50ZWdlciBULCB0aGUgbnVtYmVyIG9mIHRlc3QgY2FzZXMuPFwvcD5cclxuXHJcbjxwPkVhY2ggb2YgdGhlIG5leHQgVCBsaW5lcyB3aWxsIGNvbnRhaW4gb25lIHN0cmluZyBTIHRoYXQgd2lsbCBvbmx5IGNvbnRhaW4gdXBwZXJjYXNlIEVuZ2xpc2ggYWxwaGFiZXRzLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHRlc3QgY2FzZSwgb3V0cHV0IHRoZSBudW1iZXIgb2YgdW5pcXVlIHN0cmluZ3MgYWNyb3NzIGFsbCBwb3NzaWJsZSBVKGksIGopJiMzOTtzLjxcL3A+XHJcbiIsImhpbnQiOiI8cD5JbiB0aGUgc2Vjb25kIGV4YW1wbGUsIHRoZXJlIGFyZSBzaXggdW5pcXVlIHN0cmluZ3M6IEEsIEIsIEMsIEFCLCBCQywgQUJDLjxcL3A+XHJcblxyXG48cD5JbiB0aGUgdGhpcmQgZXhhbXBsZSwgdGhlcmUgYXJlIHRocmVlIHVuaXF1ZSBzdHJpbmc6IEEsIEIsIEFCLjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCIsImxpbWl0IjoiPHVsPlxyXG5cdDxsaT4xICZsZTsgVCAmbGU7IDEwPFwvbGk+XHJcblx0PGxpPjEgJmxlOyBOICZsZTsgMTAsMDAwJm5ic3A7PFwvbGk+XHJcbjxcL3VsPlxyXG4ifV0=