시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 128 MB 72 19 12 26.667%

문제

상근이와 선영이는 조금 독특한 농장을 운영하고 있다. 보통 농장에서는 동물이나 야채를 기르지만, 그들은 문자열을 기른다.

문자열은 연속되는 문자를 나타낸다. 문자열을 자라면서 왼쪽이나 오른쪽에 문자가 추가된다. 문자가 없어지는 경우는 없고, 중간에 문자가 추가되는 경우도 없다.

상근이와 선영이는 문자열의 성장 과정을 사진으로 찍었다. 하지만, 사진에 따로 적어놓은 것이 없기 때문에, 어떤 사진이 어떤 문자열의 사진인지를 까먹었다. 그들은 사진을 벽에 그들이 자란 순서대로 전시해놓으려고 한다. 자 이제 사진의 순서를 찾는 프로그램을 작성해보자.

각 사진은 문자열로 나타낼 수 있다. 사진의 순서는 반드시 다음과 같은 규칙을 지켜야 한다. si가 si+1의 바로 앞에 오려면, si+1은 si가 자란 형태이어야 한다. 즉, si가 si+1의 연속된 부분 문자열이어야 한다. 상근이와 선영이는 같은 사진을 여러 번 찍지 않는다. 따라서, 사진의 순서에 포함되는 사진은 모두 다르다.

상근이와 선영이가 찍은 사진이 입력으로 주어진다. 이때, 가장 긴 사진의 순서를 구하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 사진의 개수 N이 주어진다. (1 ≤ N ≤ 104) 다음 N개 줄에는 사진에 찍혀있는 문자열이 주어진다. 문자열은 알파벳 소문자로만 이루어져 있고, 길이는 1000을 넘지 않는다.

각 테스트 케이스 마다 입력으로 주어지는 문자열의 길이의 합은 106을 넘지 않는다.

입력의 마지막 줄에는 0이 하나 주어진다.

출력

각 테스트 케이스마다 가장 긴 사진의 순서의 길이를 출력한다.

예제 입력 1

6
plant
ant
cant
decant
deca
an
2
supercalifragilisticexpialidocious
rag
0

예제 출력 1

4
2
W3sicHJvYmxlbV9pZCI6IjU2OTkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJiMzhcdWM3OTBcdWM1ZjQgXHViMThkXHVjN2E1IiwiZGVzY3JpcHRpb24iOiI8cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWM2NDAgXHVjMTIwXHVjNjAxXHVjNzc0XHViMjk0IFx1Yzg3MFx1YWUwOCBcdWIzYzVcdWQyYjlcdWQ1NWMgXHViMThkXHVjN2E1XHVjNzQ0IFx1YzZiNFx1YzYwMVx1ZDU1OFx1YWNlMCBcdWM3ODhcdWIyZTQuIFx1YmNmNFx1ZDFiNSBcdWIxOGRcdWM3YTVcdWM1ZDBcdWMxMWNcdWIyOTQgXHViM2Q5XHViYjNjXHVjNzc0XHViMDk4IFx1YzU3Y1x1Y2M0NFx1Yjk3YyBcdWFlMzBcdWI5NzRcdWM5YzBcdWI5Y2MsIFx1YWRmOFx1YjRlNFx1Yzc0MCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NDQgXHVhZTMwXHViOTc4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NDAgXHVjNWYwXHVjMThkXHViNDE4XHViMjk0IFx1YmIzOFx1Yzc5MFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjhcdWIyZTQuIFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc0NCBcdWM3OTBcdWI3N2NcdWJhNzRcdWMxMWMgXHVjNjdjXHVjYWJkXHVjNzc0XHViMDk4IFx1YzYyNFx1Yjk3OFx1Y2FiZFx1YzVkMCBcdWJiMzhcdWM3OTBcdWFjMDAgXHVjZDk0XHVhYzAwXHViNDFjXHViMmU0LiBcdWJiMzhcdWM3OTBcdWFjMDAgXHVjNWM2XHVjNWI0XHVjOWMwXHViMjk0IFx1YWNiZFx1YzZiMFx1YjI5NCBcdWM1YzZcdWFjZTAsIFx1YzkxMVx1YWMwNFx1YzVkMCBcdWJiMzhcdWM3OTBcdWFjMDAgXHVjZDk0XHVhYzAwXHViNDE4XHViMjk0IFx1YWNiZFx1YzZiMFx1YjNjNCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YzY0MCBcdWMxMjBcdWM2MDFcdWM3NzRcdWIyOTQgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzU4IFx1YzEzMVx1YzdhNSBcdWFjZmNcdWM4MTVcdWM3NDQgXHVjMGFjXHVjOWM0XHVjNzNjXHViODVjIFx1Y2MwZFx1YzVjOFx1YjJlNC4gXHVkNTU4XHVjOWMwXHViOWNjLCBcdWMwYWNcdWM5YzRcdWM1ZDAgXHViNTMwXHViODVjIFx1YzgwMVx1YzViNFx1YjE5M1x1Yzc0MCBcdWFjODNcdWM3NzQgXHVjNWM2XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCwgXHVjNWI0XHViNWE0IFx1YzBhY1x1YzljNFx1Yzc3NCBcdWM1YjRcdWI1YTQgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzU4IFx1YzBhY1x1YzljNFx1Yzc3OFx1YzljMFx1Yjk3YyBcdWFlNGNcdWJhMzlcdWM1YzhcdWIyZTQuIFx1YWRmOFx1YjRlNFx1Yzc0MCBcdWMwYWNcdWM5YzRcdWM3NDQgXHViY2JkXHVjNWQwIFx1YWRmOFx1YjRlNFx1Yzc3NCBcdWM3OTBcdWI3ODAgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1YzgwNFx1YzJkY1x1ZDU3NFx1YjE5M1x1YzczY1x1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1Yzc5MCBcdWM3NzRcdWM4MWMgXHVjMGFjXHVjOWM0XHVjNzU4IFx1YzIxY1x1YzExY1x1Yjk3YyBcdWNjM2VcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU3NFx1YmNmNFx1Yzc5MC48XC9wPlxyXG5cclxuPHA+XHVhYzAxIFx1YzBhY1x1YzljNFx1Yzc0MCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWI4NWMgXHViMDk4XHVkMGMwXHViMGJjIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YzBhY1x1YzljNFx1Yzc1OCBcdWMyMWNcdWMxMWNcdWIyOTQgXHViYzE4XHViNGRjXHVjMmRjIFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NDAgXHVhZGRjXHVjZTU5XHVjNzQ0IFx1YzljMFx1Y2YxY1x1YzU3YyBcdWQ1NWNcdWIyZTQuIHM8c3ViPmk8XC9zdWI+XHVhYzAwIHM8c3ViPmkrMTxcL3N1Yj5cdWM3NTggXHViYzE0XHViODVjIFx1YzU1ZVx1YzVkMCBcdWM2MjRcdWI4MjRcdWJhNzQsIHM8c3ViPmkrMTxcL3N1Yj5cdWM3NDAgczxzdWI+aTxcL3N1Yj5cdWFjMDAgXHVjNzkwXHViNzgwIFx1ZDYxNVx1ZDBkY1x1Yzc3NFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1Yzk4OSwgczxzdWI+aTxcL3N1Yj5cdWFjMDAgczxzdWI+aSsxPFwvc3ViPlx1Yzc1OCBcdWM1ZjBcdWMxOGRcdWI0MWMgXHViZDgwXHViZDg0IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YzY0MCBcdWMxMjBcdWM2MDFcdWM3NzRcdWIyOTQgXHVhYzE5XHVjNzQwIFx1YzBhY1x1YzljNFx1Yzc0NCBcdWM1ZWNcdWI3ZWMgXHViYzg4IFx1Y2MwZFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuIFx1YjUzMFx1Yjc3Y1x1YzExYywgXHVjMGFjXHVjOWM0XHVjNzU4IFx1YzIxY1x1YzExY1x1YzVkMCBcdWQzZWNcdWQ1NjhcdWI0MThcdWIyOTQgXHVjMGFjXHVjOWM0XHVjNzQwIFx1YmFhOFx1YjQ1MCBcdWIyZTRcdWI5NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YzY0MCBcdWMxMjBcdWM2MDFcdWM3NzRcdWFjMDAgXHVjYzBkXHVjNzQwIFx1YzBhY1x1YzljNFx1Yzc3NCBcdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzRcdWI1NGMsIFx1YWMwMFx1YzdhNSBcdWFlMzQgXHVjMGFjXHVjOWM0XHVjNzU4IFx1YzIxY1x1YzExY1x1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc0MCBcdWM1ZWNcdWI3ZWMgXHVhYzFjXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWMwYWNcdWM5YzRcdWM3NTggXHVhYzFjXHVjMjE4IE5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IE4gJmxlOyAxMDxzdXA+NDxcL3N1cD4pIFx1YjJlNFx1Yzc0YyBOXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWMwYWNcdWM5YzRcdWM1ZDAgXHVjYzBkXHVkNjAwXHVjNzg4XHViMjk0IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc0MCBcdWM1NGNcdWQzMGNcdWJjYjMgXHVjMThjXHViYjM4XHVjNzkwXHViODVjXHViOWNjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWFjZTAsIFx1YWUzOFx1Yzc3NFx1YjI5NCAxMDAwXHVjNzQ0IFx1YjExOFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0IFx1YjljOFx1YjJlNCBcdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWMwXHViMjk0IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWM3NTggXHVkNTY5XHVjNzQwIDEwPHN1cD42PFwvc3VwPlx1Yzc0NCBcdWIxMThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3ODVcdWI4MjVcdWM3NTggXHViOWM4XHVjOWMwXHViOWM5IFx1YzkwNFx1YzVkMFx1YjI5NCAwXHVjNzc0IFx1ZDU1OFx1YjA5OCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI5YzhcdWIyZTQgXHVhYzAwXHVjN2E1IFx1YWUzNCBcdWMwYWNcdWM5YzRcdWM3NTggXHVjMjFjXHVjMTFjXHVjNzU4IFx1YWUzOFx1Yzc3NFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNTY5OSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6Ikdyb3dpbmcgU3RyaW5ncyIsImRlc2NyaXB0aW9uIjoiPHA+R2VuZSBhbmQgR2luYSBoYXZlIGEgcGFydGljdWxhciBraW5kIG9mIGZhcm0uIEluc3RlYWQgb2YgZ3Jvd2luZyBhbmltYWxzIGFuZCB2ZWdldGFibGVzLCBhcyBpdCBpcyB1c3VhbGx5IHRoZSBjYXNlIGluIHJlZ3VsYXIgZmFybXMsIHRoZXkgZ3JvdyBzdHJpbmdzLiBBIHN0cmluZyBpcyBhIHNlcXVlbmNlIG9mIGNoYXJhY3RlcnMuIFN0cmluZ3MgaGF2ZSB0aGUgcGFydGljdWxhcml0eSB0aGF0LCBhcyB0aGV5IGdyb3csIHRoZXkgYWRkIGNoYXJhY3RlcnMgdG8gdGhlIGxlZnQgYW5kXC9vciB0byB0aGUgcmlnaHQgb2YgdGhlbXNlbHZlcywgYnV0IHRoZXkgbmV2ZXIgbG9zZSBjaGFyYWN0ZXJzLCBub3IgaW5zZXJ0IG5ldyBjaGFyYWN0ZXJzIGluIHRoZSBtaWRkbGUuPFwvcD5cclxuXHJcbjxwPkdlbmUgYW5kIEdpbmEgaGF2ZSBhIGNvbGxlY3Rpb24gb2YgcGhvdG9zIG9mIHNvbWUgc3RyaW5ncyBhdCBkaVx1ZmIwMGVyZW50IHRpbWVzIGR1cmluZyB0aGVpciBncm93dGguIFRoZSBwcm9ibGVtIGlzIHRoYXQgdGhlIGNvbGxlY3Rpb24gaXMgbm90IGFubm90YXRlZCwgc28gdGhleSBmb3Jnb3QgdG8gd2hpY2ggc3RyaW5nIGVhY2ggcGhvdG8gYmVsb25ncyB0by4gVGhleSB3YW50IHRvIHB1dCB0b2dldGhlciBhIHdhbGwgdG8gaWxsdXN0cmF0ZSBzdHJpbmdzIGdyb3dpbmcgcHJvY2VkdXJlcywgYnV0IHRoZXkgbmVlZCB5b3VyIGhlbHAgdG8gXHVmYjAxbmQgYW4gYXBwcm9wcmlhdGUgc2VxdWVuY2Ugb2YgcGhvdG9zLjxcL3A+XHJcblxyXG48cD5FYWNoIHBob3RvIGlsbHVzdHJhdGVzIGEgc3RyaW5nLiBUaGUgc2VxdWVuY2Ugb2YgcGhvdG9zIG11c3QgYmUgc3VjaCB0aGF0IGlmIHM8c3ViPmk8XC9zdWI+IGNvbWVzIGltbWVkaWF0ZWx5IGJlZm9yZSBzPHN1Yj5pKzE8XC9zdWI+IGluIHRoZSBzZXF1ZW5jZSwgdGhlbiBzPHN1Yj5pKzE8XC9zdWI+IGlzIGEgc3RyaW5nIHRoYXQgbWF5IGhhdmUgZ3Jvd24gZnJvbSBzPHN1Yj5pPFwvc3ViPiAoaS5lLiwgczxzdWI+aTxcL3N1Yj4gYXBwZWFycyBhcyBhIGNvbnNlY3V0aXZlIHN1YnN0cmluZyBvZiBzPHN1Yj5pKzE8XC9zdWI+KS4gQWxzbywgdGhleSBkbyBub3Qgd2FudCB0byB1c2UgcmVwZWF0ZWQgcGljdHVyZXMsIHNvIGFsbCBzdHJpbmdzIGluIHRoZSBzZXF1ZW5jZSBtdXN0IGJlIGRpXHVmYjAwZXJlbnQuPFwvcD5cclxuXHJcbjxwPkdpdmVuIGEgc2V0IG9mIHN0cmluZ3MgcmVwcmVzZW50aW5nIGFsbCBhdmFpbGFibGUgcGhvdG9zLCB5b3VyIGpvYiBpcyB0byBjYWxjdWxhdGUgdGhlIHNpemUgb2YgdGhlIGxhcmdlc3Qgc2VxdWVuY2UgdGhleSBjYW4gcHJvZHVjZSBmb2xsb3dpbmcgdGhlIGd1aWRlbGluZXMgYWJvdmUuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5FYWNoIHRlc3QgY2FzZSBpcyBnaXZlbiB1c2luZyBzZXZlcmFsIGxpbmVzLiBUaGUgXHVmYjAxcnN0IGxpbmUgY29udGFpbnMgYW4gaW50ZWdlciBOIHJlcHJlc2VudGluZyB0aGUgbnVtYmVyIG9mIHN0cmluZ3MgaW4gdGhlIHNldCAoMSAmbGU7IE4gJmxlOyAxMDxzdXA+NDxcL3N1cD4pLiBFYWNoIG9mIHRoZSBmb2xsb3dpbmcgTiBsaW5lcyBjb250YWlucyBhIGRpXHVmYjAwZXJlbnQgbm9uLWVtcHR5IHN0cmluZyBvZiBhdCBtb3N0IDEwMDAgbG93ZXJjYXNlIGxldHRlcnMgb2YgdGhlIEVuZ2xpc2ggYWxwaGFiZXQuIFdpdGhpbiBlYWNoIHRlc3QgY2FzZSwgdGhlIHN1bSBvZiB0aGUgbGVuZ3RocyBvZiBhbGwgc3RyaW5ncyBpcyBhdCBtb3N0IDEwPHN1cD42PFwvc3VwPi48XC9wPlxyXG5cclxuPHA+VGhlIGxhc3QgdGVzdCBjYXNlIGlzIGZvbGxvd2VkIGJ5IGEgbGluZSBjb250YWluaW5nIG9uZSB6ZXJvLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHRlc3QgY2FzZSBvdXRwdXQgYSBzaW5nbGUgbGluZSB3aXRoIGEgc2luZ2xlIGludGVnZXIgcmVwcmVzZW50aW5nIHRoZSBzaXplIG9mIHRoZSBsYXJnZXN0IHNlcXVlbmNlIG9mIHBob3RvcyB0aGF0IGNhbiBiZSBwcm9kdWNlZC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=