시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 256 MB 73 41 32 54.237%

문제

문자열 분석은 DNA와 단백질 분자의 연구를 진행하기 위해 생물학과 화학 분야에서 종종 사용된다. 문자열 분석을 하는 데 있어, 긴 문자열에서 얼마나 많은 부분 문자열이 (적어도 두 번) 반복되는지 찾아내는 것이 중요한 문제이다.

이 문제에서 최대 100 000개의 알파벳 문자열이 주어지면, 여러분은 그 문자열 중 모든 반복되는 부분 문자열의 개수를 찾아야한다. 이 때, 두 번 이상 등장하는 모든 유일한 부분 문자열을 세어야 한다. 예를 들어, 주어지는 문자열이 "aabaab"이면 반복되는 부분 문자열은 총 5개가 있다 : "a", "aa", "aab", "ab", "b". 또, 주어지는 문자열이 "aaaaa"이면 반복되는 부분 문자열은 총 4개가 있다 : "a", "aa", "aaa", "aaaa". 반복되는 부분 문자열은 겹칠 수도 있다는 것에 유의하도록 하자 (두 번째 예시의 "aaaa").

입력

첫 줄에는 테스트 케이스의 수 T가 정수로 주어진다. 입력은 최대 10개의 테스트 케이스로 이루어진다.

각 테스트 케이스마다 첫 번째 줄에 알파벳으로만 이루어진 문자열이 주어진다. 문자열의 길이는 최대 100 000이다.

출력

각 테스트 케이스마다, 주어지는 문자열에서 반복되는 모든 유일한 부분 문자열의 개수를 출력한다. 이 때, 답은 부호있는 32비트 정수형으로 항상 표현할 수 있다.

예제 입력 1

3
aabaab
aaaaa
AaAaA

예제 출력 1

5
4
5

힌트

W3sicHJvYmxlbV9pZCI6IjEwNDEzIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHViYzE4XHViY2Y1XHViNDE4XHViMjk0IFx1YmQ4MFx1YmQ4NCBcdWJiMzhcdWM3OTBcdWM1ZjQiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YmIzOFx1Yzc5MFx1YzVmNCBcdWJkODRcdWMxMWRcdWM3NDAgRE5BXHVjNjQwIFx1YjJlOFx1YmMzMVx1YzljOCBcdWJkODRcdWM3OTBcdWM3NTggXHVjNWYwXHVhZDZjXHViOTdjIFx1YzljNFx1ZDU4OVx1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NzQmbmJzcDtcdWMwZGRcdWJiM2NcdWQ1NTlcdWFjZmMgXHVkNjU0XHVkNTU5IFx1YmQ4NFx1YzU3Y1x1YzVkMFx1YzExYyBcdWM4ODVcdWM4ODUgXHVjMGFjXHVjNmE5XHViNDFjXHViMmU0LiBcdWJiMzhcdWM3OTBcdWM1ZjQgXHViZDg0XHVjMTFkXHVjNzQ0IFx1ZDU1OFx1YjI5NCBcdWIzNzAgXHVjNzg4XHVjNWI0LCZuYnNwO1x1YWUzNCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM1ZDBcdWMxMWMmbmJzcDtcdWM1YmNcdWI5YzhcdWIwOTggXHViOWNlXHVjNzQwIFx1YmQ4MFx1YmQ4NCZuYnNwO1x1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NCAoXHVjODAxXHVjNWI0XHViM2M0IFx1YjQ1MCBcdWJjODgpIFx1YmMxOFx1YmNmNVx1YjQxOFx1YjI5NFx1YzljMCBcdWNjM2VcdWM1NDRcdWIwYjRcdWIyOTQgXHVhYzgzXHVjNzc0IFx1YzkxMVx1YzY5NFx1ZDU1YyBcdWJiMzhcdWM4MWNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc3NCBcdWJiMzhcdWM4MWNcdWM1ZDBcdWMxMWMmbmJzcDtcdWNkNWNcdWIzMDAgMTAwIDAwMFx1YWMxY1x1Yzc1OCBcdWM1NGNcdWQzMGNcdWJjYjMgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljMFx1YmE3NCwgXHVjNWVjXHViN2VjXHViZDg0XHVjNzQwJm5ic3A7XHVhZGY4IFx1YmIzOFx1Yzc5MFx1YzVmNCZuYnNwO1x1YzkxMSBcdWJhYThcdWI0ZTAmbmJzcDtcdWJjMThcdWJjZjVcdWI0MThcdWIyOTQgXHViZDgwXHViZDg0IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVjYzNlXHVjNTQ0XHVjNTdjXHVkNTVjXHViMmU0LiBcdWM3NzQgXHViNTRjLCBcdWI0NTAgXHViYzg4IFx1Yzc3NFx1YzBjMSBcdWI0ZjFcdWM3YTVcdWQ1NThcdWIyOTQmbmJzcDtcdWJhYThcdWI0ZTAgXHVjNzIwXHVjNzdjXHVkNTVjIFx1YmQ4MFx1YmQ4NCZuYnNwO1x1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc0NCBcdWMxMzhcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LiZuYnNwO1x1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsJm5ic3A7XHVjOGZjXHVjNWI0XHVjOWMwXHViMjk0IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NCAmcXVvdDthYWJhYWImcXVvdDtcdWM3NzRcdWJhNzQgXHViYzE4XHViY2Y1XHViNDE4XHViMjk0IFx1YmQ4MFx1YmQ4NCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NDAgXHVjZDFkIDVcdWFjMWNcdWFjMDAgXHVjNzg4XHViMmU0IDogJnF1b3Q7YSZxdW90OywgJnF1b3Q7YWEmcXVvdDssICZxdW90O2FhYiZxdW90OywgJnF1b3Q7YWImcXVvdDssICZxdW90O2ImcXVvdDsuIFx1YjYxMCwgXHVjOGZjXHVjNWI0XHVjOWMwXHViMjk0IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NCAmcXVvdDthYWFhYSZxdW90O1x1Yzc3NFx1YmE3NCBcdWJjMThcdWJjZjVcdWI0MThcdWIyOTQgXHViZDgwXHViZDg0IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc0MCBcdWNkMWQgNFx1YWMxY1x1YWMwMCBcdWM3ODhcdWIyZTQgOiZuYnNwOyZxdW90O2EmcXVvdDssICZxdW90O2FhJnF1b3Q7LCAmcXVvdDthYWEmcXVvdDssICZxdW90O2FhYWEmcXVvdDsuIFx1YmMxOFx1YmNmNVx1YjQxOFx1YjI5NCBcdWJkODBcdWJkODQgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzQwIFx1YWNiOVx1Y2U2MCBcdWMyMThcdWIzYzQgXHVjNzg4XHViMmU0XHViMjk0IFx1YWM4M1x1YzVkMCBcdWM3MjBcdWM3NThcdWQ1NThcdWIzYzRcdWI4NWQgXHVkNTU4XHVjNzkwIChcdWI0NTAgXHViYzg4XHVjOWY4IFx1YzYwOFx1YzJkY1x1Yzc1OCAmcXVvdDthYWFhJnF1b3Q7KS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWMyMTggVFx1YWMwMCBcdWM4MTVcdWMyMThcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3ODVcdWI4MjVcdWM3NDAgXHVjZDVjXHViMzAwIDEwXHVhYzFjXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjljOFx1YjJlNCBcdWNjYWIgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMCBcdWM1NGNcdWQzMGNcdWJjYjNcdWM3M2NcdWI4NWNcdWI5Y2MgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWIyOTQgXHVjZDVjXHViMzAwIDEwMCAwMDBcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI5YzhcdWIyZTQsIFx1YzhmY1x1YzViNFx1YzljMFx1YjI5NCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM1ZDBcdWMxMWMgXHViYzE4XHViY2Y1XHViNDE4XHViMjk0IFx1YmFhOFx1YjRlMCZuYnNwO1x1YzcyMFx1Yzc3Y1x1ZDU1YyBcdWJkODBcdWJkODQgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1Yzc3NCBcdWI1NGMsIFx1YjJmNVx1Yzc0MCBcdWJkODBcdWQ2MzhcdWM3ODhcdWIyOTQgMzJcdWJlNDRcdWQyYjggXHVjODE1XHVjMjE4XHVkNjE1XHVjNzNjXHViODVjIFx1ZDU2ZFx1YzBjMSBcdWQ0NWNcdWQ2MDRcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIxMDQxMyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlJlcGVhdGVkIFN1YnN0cmluZ3MiLCJkZXNjcmlwdGlvbiI6IjxwPlN0cmluZyBhbmFseXNpcyBvZnRlbiBhcmlzZXMgaW4gYXBwbGljYXRpb25zIGZyb20gYmlvbG9neSBhbmQgY2hlbWlzdHJ5LCBzdWNoIGFzIHRoZSBzdHVkeSBvZiBETkEgYW5kIHByb3RlaW4gbW9sZWN1bGVzLiBPbmUgaW50ZXJlc3RpbmcgcHJvYmxlbSBpcyB0byBmaW5kIGhvdyBtYW55IHN1YnN0cmluZ3MgYXJlIHJlcGVhdGVkIChhdCBsZWFzdCB0d2ljZSkgaW4gYSBsb25nIHN0cmluZy48XC9wPlxyXG5cclxuPHA+SW4gdGhpcyBwcm9ibGVtLCB5b3Ugd2lsbCB3cml0ZSBhIHByb2dyYW0gdG8gZmluZCB0aGUgdG90YWwgbnVtYmVyIG9mIHJlcGVhdGVkIHN1YnN0cmluZ3MgaW4gYSBzdHJpbmcgb2YgYXQgbW9zdCAxMDAgMDAwIGFscGhhYmV0aWMgY2hhcmFjdGVycy4gQW55IHVuaXF1ZSBzdWJzdHJpbmcgdGhhdCBvY2N1cnMgbW9yZSB0aGFuIG9uY2UgaXMgY291bnRlZC4gQXMgYW4gZXhhbXBsZSwgaWYgdGhlIHN0cmluZyBpcyAmbGRxdW87YWFiYWFiJnJkcXVvOywgdGhlcmUgYXJlIDUgcmVwZWF0ZWQgc3Vic3RyaW5nczogJmxkcXVvO2EmcmRxdW87LCAmbGRxdW87YWEmcmRxdW87LCAmbGRxdW87YWFiJnJkcXVvOywgJmxkcXVvO2FiJnJkcXVvOywgJmxkcXVvO2ImcmRxdW87LiBJZiB0aGUgc3RyaW5nIGlzICZsZHF1bzthYWFhYSZyZHF1bzssIHRoZSByZXBlYXRlZCBzdWJzdHJpbmdzIGFyZSAmbGRxdW87YSZyZHF1bzssICZsZHF1bzthYSZyZHF1bzssICZsZHF1bzthYWEmcmRxdW87LCAmbGRxdW87YWFhYSZyZHF1bzsuIE5vdGUgdGhhdCByZXBlYXRlZCBvY2N1cnJlbmNlcyBvZiBhIHN1YnN0cmluZyBtYXkgb3ZlcmxhcCAoZS5nLiAmbGRxdW87YWFhYSZyZHF1bzsgaW4gdGhlIHNlY29uZCBjYXNlKS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBpbnB1dCBjb25zaXN0cyBvZiBhdCBtb3N0IDEwIGNhc2VzLiBUaGUgZmlyc3QgbGluZSBjb250YWlucyBhIHBvc2l0aXZlIGludGVnZXIsIHNwZWNpZnlpbmcgdGhlIG51bWJlciBvZiBjYXNlcyB0byBmb2xsb3cuIEVhY2ggb2YgdGhlIGZvbGxvd2luZyBsaW5lIGNvbnRhaW5zIGEgbm9uZW1wdHkgc3RyaW5nIG9mIHVwIHRvIDEwMCAwMDAgYWxwaGFiZXRpYyBjaGFyYWN0ZXJzLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIGxpbmUgb2YgaW5wdXQsIG91dHB1dCBvbmUgbGluZSBjb250YWluaW5nIHRoZSBudW1iZXIgb2YgdW5pcXVlIHN1YnN0cmluZ3MgdGhhdCBhcmUgcmVwZWF0ZWQuIFlvdSBtYXkgYXNzdW1lIHRoYXQgdGhlIGNvcnJlY3QgYW5zd2VyIGZpdHMgaW4gYSBzaWduZWQgMzItYml0IGludGVnZXIuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d