시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 256 MB 95 59 42 58.333%

문제

문자열 분석은 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
W3sicHJvYmxlbV9pZCI6IjEwNDEzIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHViYzE4XHViY2Y1XHViNDE4XHViMjk0IFx1YmQ4MFx1YmQ4NCBcdWJiMzhcdWM3OTBcdWM1ZjQiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YmIzOFx1Yzc5MFx1YzVmNCBcdWJkODRcdWMxMWRcdWM3NDAgRE5BXHVjNjQwIFx1YjJlOFx1YmMzMVx1YzljOCBcdWJkODRcdWM3OTBcdWM3NTggXHVjNWYwXHVhZDZjXHViOTdjIFx1YzljNFx1ZDU4OVx1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NzQmbmJzcDtcdWMwZGRcdWJiM2NcdWQ1NTlcdWFjZmMgXHVkNjU0XHVkNTU5IFx1YmQ4NFx1YzU3Y1x1YzVkMFx1YzExYyBcdWM4ODVcdWM4ODUgXHVjMGFjXHVjNmE5XHViNDFjXHViMmU0LiBcdWJiMzhcdWM3OTBcdWM1ZjQgXHViZDg0XHVjMTFkXHVjNzQ0IFx1ZDU1OFx1YjI5NCBcdWIzNzAgXHVjNzg4XHVjNWI0LCZuYnNwO1x1YWUzNCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM1ZDBcdWMxMWMmbmJzcDtcdWM1YmNcdWI5YzhcdWIwOTggXHViOWNlXHVjNzQwIFx1YmQ4MFx1YmQ4NCZuYnNwO1x1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NCAoXHVjODAxXHVjNWI0XHViM2M0IFx1YjQ1MCBcdWJjODgpIFx1YmMxOFx1YmNmNVx1YjQxOFx1YjI5NFx1YzljMCBcdWNjM2VcdWM1NDRcdWIwYjRcdWIyOTQgXHVhYzgzXHVjNzc0IFx1YzkxMVx1YzY5NFx1ZDU1YyBcdWJiMzhcdWM4MWNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc3NCBcdWJiMzhcdWM4MWNcdWM1ZDBcdWMxMWMmbmJzcDtcdWNkNWNcdWIzMDAgMTAwIDAwMFx1YWMxY1x1Yzc1OCBcdWM1NGNcdWQzMGNcdWJjYjMgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljMFx1YmE3NCwgXHVjNWVjXHViN2VjXHViZDg0XHVjNzQwJm5ic3A7XHVhZGY4IFx1YmIzOFx1Yzc5MFx1YzVmNCZuYnNwO1x1YzkxMSBcdWJhYThcdWI0ZTAmbmJzcDtcdWJjMThcdWJjZjVcdWI0MThcdWIyOTQgXHViZDgwXHViZDg0IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVjYzNlXHVjNTQ0XHVjNTdjXHVkNTVjXHViMmU0LiBcdWM3NzRcdWI1NGMsIFx1YjQ1MCBcdWJjODggXHVjNzc0XHVjMGMxIFx1YjRmMVx1YzdhNVx1ZDU1OFx1YjI5NCZuYnNwO1x1YmFhOFx1YjRlMCBcdWM3MjBcdWM3N2NcdWQ1NWMgXHViZDgwXHViZDg0Jm5ic3A7XHViYjM4XHVjNzkwXHVjNWY0XHVjNzQ0IFx1YzEzOFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuJm5ic3A7XHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwmbmJzcDtcdWM4ZmNcdWM1YjRcdWM5YzBcdWIyOTQgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzc0ICZxdW90O2FhYmFhYiZxdW90O1x1Yzc3NFx1YmE3NCBcdWJjMThcdWJjZjVcdWI0MThcdWIyOTQgXHViZDgwXHViZDg0IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc0MCBcdWNkMWQgNVx1YWMxY1x1YWMwMCBcdWM3ODhcdWIyZTQgOiAmcXVvdDthJnF1b3Q7LCAmcXVvdDthYSZxdW90OywgJnF1b3Q7YWFiJnF1b3Q7LCAmcXVvdDthYiZxdW90OywgJnF1b3Q7YiZxdW90Oy4gXHViNjEwLCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWIyOTQgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzc0ICZxdW90O2FhYWFhJnF1b3Q7XHVjNzc0XHViYTc0IFx1YmMxOFx1YmNmNVx1YjQxOFx1YjI5NCBcdWJkODBcdWJkODQgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzQwIFx1Y2QxZCA0XHVhYzFjXHVhYzAwIFx1Yzc4OFx1YjJlNCA6Jm5ic3A7JnF1b3Q7YSZxdW90OywgJnF1b3Q7YWEmcXVvdDssICZxdW90O2FhYSZxdW90OywgJnF1b3Q7YWFhYSZxdW90Oy4gXHViYzE4XHViY2Y1XHViNDE4XHViMjk0IFx1YmQ4MFx1YmQ4NCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NDAgXHVhY2I5XHVjZTYwIFx1YzIxOFx1YjNjNCBcdWM3ODhcdWIyZTRcdWIyOTQgXHVhYzgzXHVjNWQwIFx1YzcyMFx1Yzc1OFx1ZDU1OFx1YjNjNFx1Yjg1ZCBcdWQ1NThcdWM3OTAgKFx1YjQ1MCBcdWJjODhcdWM5ZjggXHVjNjA4XHVjMmRjXHVjNzU4ICZxdW90O2FhYWEmcXVvdDspLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YzIxOCBUXHVhYzAwIFx1YzgxNVx1YzIxOFx1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzc4NVx1YjgyNVx1Yzc0MCBcdWNkNWNcdWIzMDAgMTBcdWFjMWNcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViOWM4XHViMmU0IFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzU0Y1x1ZDMwY1x1YmNiM1x1YzczY1x1Yjg1Y1x1YjljYyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViYjM4XHVjNzkwXHVjNWY0XHVjNzU4IFx1YWUzOFx1Yzc3NFx1YjI5NCBcdWNkNWNcdWIzMDAgMTAwIDAwMFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjljOFx1YjJlNCwgXHVjOGZjXHVjNWI0XHVjOWMwXHViMjk0IFx1YmIzOFx1Yzc5MFx1YzVmNFx1YzVkMFx1YzExYyBcdWJjMThcdWJjZjVcdWI0MThcdWIyOTQgXHViYWE4XHViNGUwJm5ic3A7XHVjNzIwXHVjNzdjXHVkNTVjIFx1YmQ4MFx1YmQ4NCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVjNzc0XHViNTRjLCBcdWIyZjVcdWM3NDAgXHViZDgwXHVkNjM4XHVjNzg4XHViMjk0IDMyXHViZTQ0XHVkMmI4IFx1YzgxNVx1YzIxOFx1ZDYxNVx1YzczY1x1Yjg1YyBcdWQ1NmRcdWMwYzEgXHVkNDVjXHVkNjA0XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMTA0MTMiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJSZXBlYXRlZCBTdWJzdHJpbmdzIiwiZGVzY3JpcHRpb24iOiI8cD5TdHJpbmcgYW5hbHlzaXMgb2Z0ZW4gYXJpc2VzIGluIGFwcGxpY2F0aW9ucyBmcm9tIGJpb2xvZ3kgYW5kIGNoZW1pc3RyeSwgc3VjaCBhcyB0aGUgc3R1ZHkgb2YgRE5BIGFuZCBwcm90ZWluIG1vbGVjdWxlcy4gT25lIGludGVyZXN0aW5nIHByb2JsZW0gaXMgdG8gZmluZCBob3cgbWFueSBzdWJzdHJpbmdzIGFyZSByZXBlYXRlZCAoYXQgbGVhc3QgdHdpY2UpIGluIGEgbG9uZyBzdHJpbmcuPFwvcD5cclxuXHJcbjxwPkluIHRoaXMgcHJvYmxlbSwgeW91IHdpbGwgd3JpdGUgYSBwcm9ncmFtIHRvIGZpbmQgdGhlIHRvdGFsIG51bWJlciBvZiByZXBlYXRlZCBzdWJzdHJpbmdzIGluIGEgc3RyaW5nIG9mIGF0IG1vc3QgMTAwIDAwMCBhbHBoYWJldGljIGNoYXJhY3RlcnMuIEFueSB1bmlxdWUgc3Vic3RyaW5nIHRoYXQgb2NjdXJzIG1vcmUgdGhhbiBvbmNlIGlzIGNvdW50ZWQuIEFzIGFuIGV4YW1wbGUsIGlmIHRoZSBzdHJpbmcgaXMgJmxkcXVvO2FhYmFhYiZyZHF1bzssIHRoZXJlIGFyZSA1IHJlcGVhdGVkIHN1YnN0cmluZ3M6ICZsZHF1bzthJnJkcXVvOywgJmxkcXVvO2FhJnJkcXVvOywgJmxkcXVvO2FhYiZyZHF1bzssICZsZHF1bzthYiZyZHF1bzssICZsZHF1bztiJnJkcXVvOy4gSWYgdGhlIHN0cmluZyBpcyAmbGRxdW87YWFhYWEmcmRxdW87LCB0aGUgcmVwZWF0ZWQgc3Vic3RyaW5ncyBhcmUgJmxkcXVvO2EmcmRxdW87LCAmbGRxdW87YWEmcmRxdW87LCAmbGRxdW87YWFhJnJkcXVvOywgJmxkcXVvO2FhYWEmcmRxdW87LiBOb3RlIHRoYXQgcmVwZWF0ZWQgb2NjdXJyZW5jZXMgb2YgYSBzdWJzdHJpbmcgbWF5IG92ZXJsYXAgKGUuZy4gJmxkcXVvO2FhYWEmcmRxdW87IGluIHRoZSBzZWNvbmQgY2FzZSkuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgaW5wdXQgY29uc2lzdHMgb2YgYXQgbW9zdCAxMCBjYXNlcy4gVGhlIGZpcnN0IGxpbmUgY29udGFpbnMgYSBwb3NpdGl2ZSBpbnRlZ2VyLCBzcGVjaWZ5aW5nIHRoZSBudW1iZXIgb2YgY2FzZXMgdG8gZm9sbG93LiBFYWNoIG9mIHRoZSBmb2xsb3dpbmcgbGluZSBjb250YWlucyBhIG5vbmVtcHR5IHN0cmluZyBvZiB1cCB0byAxMDAgMDAwIGFscGhhYmV0aWMgY2hhcmFjdGVycy48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCBsaW5lIG9mIGlucHV0LCBvdXRwdXQgb25lIGxpbmUgY29udGFpbmluZyB0aGUgbnVtYmVyIG9mIHVuaXF1ZSBzdWJzdHJpbmdzIHRoYXQgYXJlIHJlcGVhdGVkLiBZb3UgbWF5IGFzc3VtZSB0aGF0IHRoZSBjb3JyZWN0IGFuc3dlciBmaXRzIGluIGEgc2lnbmVkIDMyLWJpdCBpbnRlZ2VyLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==