시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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+aSsxPFwvc3ViPlx1Yzc1OCBcdWM1ZjBcdWMxOGRcdWI0MWMgXHViZDgwXHViZDg0IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YzY0MCBcdWMxMjBcdWM2MDFcdWM3NzRcdWIyOTQgXHVhYzE5XHVjNzQwIFx1YzBhY1x1YzljNFx1Yzc0NCBcdWM1ZWNcdWI3ZWMgXHViYzg4IFx1Y2MwZFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuIFx1YjUzMFx1Yjc3Y1x1YzExYywgXHVjMGFjXHVjOWM0XHVjNzU4IFx1YzIxY1x1YzExY1x1YzVkMCBcdWQzZWNcdWQ1NjhcdWI0MThcdWIyOTQgXHVjMGFjXHVjOWM0XHVjNzQwIFx1YmFhOFx1YjQ1MCBcdWIyZTRcdWI5NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YzY0MCBcdWMxMjBcdWM2MDFcdWM3NzRcdWFjMDAgXHVjYzBkXHVjNzQwIFx1YzBhY1x1YzljNFx1Yzc3NCBcdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzQgXHViNTRjLCBcdWFjMDBcdWM3YTUgXHVhZTM0IFx1YzBhY1x1YzljNFx1Yzc1OCBcdWMyMWNcdWMxMWNcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3NDAgXHVjNWVjXHViN2VjIFx1YWMxY1x1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjMGFjXHVjOWM0XHVjNzU4IFx1YWMxY1x1YzIxOCBOXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBOICZsZTsgMTA8c3VwPjQ8XC9zdXA+KSBcdWIyZTRcdWM3NGMgTlx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjMGFjXHVjOWM0XHVjNWQwIFx1Y2MwZFx1ZDYwMFx1Yzc4OFx1YjI5NCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NDAgXHVjNTRjXHVkMzBjXHViY2IzIFx1YzE4Y1x1YmIzOFx1Yzc5MFx1Yjg1Y1x1YjljYyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHVhY2UwLCBcdWFlMzhcdWM3NzRcdWIyOTQgMTAwMFx1Yzc0NCBcdWIxMThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNCBcdWI5YzhcdWIyZTQgXHVjNzg1XHViODI1XHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljMFx1YjI5NCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NTggXHVhZTM4XHVjNzc0XHVjNzU4IFx1ZDU2OVx1Yzc0MCAxMDxzdXA+NjxcL3N1cD5cdWM3NDQgXHViMTE4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzg1XHViODI1XHVjNzU4IFx1YjljOFx1YzljMFx1YjljOSBcdWM5MDRcdWM1ZDBcdWIyOTQgMFx1Yzc3NCBcdWQ1NThcdWIwOTggXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViOWM4XHViMmU0IFx1YWMwMFx1YzdhNSBcdWFlMzQgXHVjMGFjXHVjOWM0XHVjNzU4IFx1YzIxY1x1YzExY1x1Yzc1OCBcdWFlMzhcdWM3NzRcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjU2OTkiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJHcm93aW5nIFN0cmluZ3MiLCJkZXNjcmlwdGlvbiI6IjxwPkdlbmUgYW5kIEdpbmEgaGF2ZSBhIHBhcnRpY3VsYXIga2luZCBvZiBmYXJtLiBJbnN0ZWFkIG9mIGdyb3dpbmcgYW5pbWFscyBhbmQgdmVnZXRhYmxlcywgYXMgaXQgaXMgdXN1YWxseSB0aGUgY2FzZSBpbiByZWd1bGFyIGZhcm1zLCB0aGV5IGdyb3cgc3RyaW5ncy4gQSBzdHJpbmcgaXMgYSBzZXF1ZW5jZSBvZiBjaGFyYWN0ZXJzLiBTdHJpbmdzIGhhdmUgdGhlIHBhcnRpY3VsYXJpdHkgdGhhdCwgYXMgdGhleSBncm93LCB0aGV5IGFkZCBjaGFyYWN0ZXJzIHRvIHRoZSBsZWZ0IGFuZFwvb3IgdG8gdGhlIHJpZ2h0IG9mIHRoZW1zZWx2ZXMsIGJ1dCB0aGV5IG5ldmVyIGxvc2UgY2hhcmFjdGVycywgbm9yIGluc2VydCBuZXcgY2hhcmFjdGVycyBpbiB0aGUgbWlkZGxlLjxcL3A+XHJcblxyXG48cD5HZW5lIGFuZCBHaW5hIGhhdmUgYSBjb2xsZWN0aW9uIG9mIHBob3RvcyBvZiBzb21lIHN0cmluZ3MgYXQgZGlcdWZiMDBlcmVudCB0aW1lcyBkdXJpbmcgdGhlaXIgZ3Jvd3RoLiBUaGUgcHJvYmxlbSBpcyB0aGF0IHRoZSBjb2xsZWN0aW9uIGlzIG5vdCBhbm5vdGF0ZWQsIHNvIHRoZXkgZm9yZ290IHRvIHdoaWNoIHN0cmluZyBlYWNoIHBob3RvIGJlbG9uZ3MgdG8uIFRoZXkgd2FudCB0byBwdXQgdG9nZXRoZXIgYSB3YWxsIHRvIGlsbHVzdHJhdGUgc3RyaW5ncyBncm93aW5nIHByb2NlZHVyZXMsIGJ1dCB0aGV5IG5lZWQgeW91ciBoZWxwIHRvIFx1ZmIwMW5kIGFuIGFwcHJvcHJpYXRlIHNlcXVlbmNlIG9mIHBob3Rvcy48XC9wPlxyXG5cclxuPHA+RWFjaCBwaG90byBpbGx1c3RyYXRlcyBhIHN0cmluZy4gVGhlIHNlcXVlbmNlIG9mIHBob3RvcyBtdXN0IGJlIHN1Y2ggdGhhdCBpZiBzPHN1Yj5pPFwvc3ViPiBjb21lcyBpbW1lZGlhdGVseSBiZWZvcmUgczxzdWI+aSsxPFwvc3ViPiBpbiB0aGUgc2VxdWVuY2UsIHRoZW4gczxzdWI+aSsxPFwvc3ViPiBpcyBhIHN0cmluZyB0aGF0IG1heSBoYXZlIGdyb3duIGZyb20gczxzdWI+aTxcL3N1Yj4gKGkuZS4sIHM8c3ViPmk8XC9zdWI+IGFwcGVhcnMgYXMgYSBjb25zZWN1dGl2ZSBzdWJzdHJpbmcgb2YgczxzdWI+aSsxPFwvc3ViPikuIEFsc28sIHRoZXkgZG8gbm90IHdhbnQgdG8gdXNlIHJlcGVhdGVkIHBpY3R1cmVzLCBzbyBhbGwgc3RyaW5ncyBpbiB0aGUgc2VxdWVuY2UgbXVzdCBiZSBkaVx1ZmIwMGVyZW50LjxcL3A+XHJcblxyXG48cD5HaXZlbiBhIHNldCBvZiBzdHJpbmdzIHJlcHJlc2VudGluZyBhbGwgYXZhaWxhYmxlIHBob3RvcywgeW91ciBqb2IgaXMgdG8gY2FsY3VsYXRlIHRoZSBzaXplIG9mIHRoZSBsYXJnZXN0IHNlcXVlbmNlIHRoZXkgY2FuIHByb2R1Y2UgZm9sbG93aW5nIHRoZSBndWlkZWxpbmVzIGFib3ZlLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+RWFjaCB0ZXN0IGNhc2UgaXMgZ2l2ZW4gdXNpbmcgc2V2ZXJhbCBsaW5lcy4gVGhlIFx1ZmIwMXJzdCBsaW5lIGNvbnRhaW5zIGFuIGludGVnZXIgTiByZXByZXNlbnRpbmcgdGhlIG51bWJlciBvZiBzdHJpbmdzIGluIHRoZSBzZXQgKDEgJmxlOyBOICZsZTsgMTA8c3VwPjQ8XC9zdXA+KS4gRWFjaCBvZiB0aGUgZm9sbG93aW5nIE4gbGluZXMgY29udGFpbnMgYSBkaVx1ZmIwMGVyZW50IG5vbi1lbXB0eSBzdHJpbmcgb2YgYXQgbW9zdCAxMDAwIGxvd2VyY2FzZSBsZXR0ZXJzIG9mIHRoZSBFbmdsaXNoIGFscGhhYmV0LiBXaXRoaW4gZWFjaCB0ZXN0IGNhc2UsIHRoZSBzdW0gb2YgdGhlIGxlbmd0aHMgb2YgYWxsIHN0cmluZ3MgaXMgYXQgbW9zdCAxMDxzdXA+NjxcL3N1cD4uPFwvcD5cclxuXHJcbjxwPlRoZSBsYXN0IHRlc3QgY2FzZSBpcyBmb2xsb3dlZCBieSBhIGxpbmUgY29udGFpbmluZyBvbmUgemVyby48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2Ugb3V0cHV0IGEgc2luZ2xlIGxpbmUgd2l0aCBhIHNpbmdsZSBpbnRlZ2VyIHJlcHJlc2VudGluZyB0aGUgc2l6ZSBvZiB0aGUgbGFyZ2VzdCBzZXF1ZW5jZSBvZiBwaG90b3MgdGhhdCBjYW4gYmUgcHJvZHVjZWQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d