시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 256 MB 248 143 126 59.716%

문제

한신이는 대학교에서 "복붙의 달인"으로 유명하다. 한신이는 타이핑 속도가 느리기 때문에 대학에서 가능한 모든 일을 복붙으로 해결한다. 그는 n개의 문자를 입력하는데 있어서 n초의 시간이 걸리지만 뛰어난 "붙여넣기" 스킬을 이용하면 어떠한 갯수의 문자도 단 1초만에 타이핑 할 수 있다. 만약 한신이가 "bana"를 복사한 상태에서 "banana"를 타이핑한다면,"bana" 붙여넣기 1초, 'n'입력, 'a'입력해서 총 3초가 걸린다. 한신이가 클립보드에 저장한 p를 알고 있을때 s를 입력하는데 걸리는 최소 시간을 계산해보자!

입력

첫번째 줄 입력으로는 정수 T(T<=25)를 테스트 케이스로 입력받는다. 각 테스트케이스는 한 줄에 2개의 문자열 s와 p가 공백으로 구분되어 입력되며  한신이는 p를 복사하여 s를 만들어 내는 것을 목표로 한다. s의 최대 길이 10000이고, p의 최대 길이는 100이다.

출력

각 테스트 케이스에 맞는 한신이가 p를 이용하여 s를 타이핑 할때 걸리는 최소 시간(초 단위)을 출력하라!

예제 입력 1

2
banana bana
asakusa sa

예제 출력 1

3
5

힌트

W3sicHJvYmxlbV9pZCI6IjExMDA4IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHViY2Y1XHViZDk5XHVjNzU4IFx1YjJlY1x1Yzc3OCIsImRlc2NyaXB0aW9uIjoiPHA+XHVkNTVjXHVjMmUwXHVjNzc0XHViMjk0IFx1YjMwMFx1ZDU1OVx1YWQ1MFx1YzVkMFx1YzExYyZuYnNwOyZxdW90O1x1YmNmNVx1YmQ5OVx1Yzc1OCBcdWIyZWNcdWM3NzgmcXVvdDtcdWM3M2NcdWI4NWMgXHVjNzIwXHViYTg1XHVkNTU4XHViMmU0LiBcdWQ1NWNcdWMyZTBcdWM3NzRcdWIyOTQmbmJzcDtcdWQwYzBcdWM3NzRcdWQ1NTEgXHVjMThkXHViM2M0XHVhYzAwIFx1YjI5MFx1YjlhY1x1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAmbmJzcDtcdWIzMDBcdWQ1NTlcdWM1ZDBcdWMxMWMgXHVhYzAwXHViMmE1XHVkNTVjIFx1YmFhOFx1YjRlMCBcdWM3N2NcdWM3NDQgXHViY2Y1XHViZDk5XHVjNzNjXHViODVjIFx1ZDU3NFx1YWNiMFx1ZDU1Y1x1YjJlNC4mbmJzcDtcdWFkZjhcdWIyOTQgblx1YWMxY1x1Yzc1OCBcdWJiMzhcdWM3OTBcdWI5N2MgXHVjNzg1XHViODI1XHVkNTU4XHViMjk0XHViMzcwIFx1Yzc4OFx1YzViNFx1YzExYyBuXHVjZDA4XHVjNzU4IFx1YzJkY1x1YWMwNFx1Yzc3NCBcdWFjNzhcdWI5YWNcdWM5YzBcdWI5Y2MmbmJzcDtcdWI2ZjBcdWM1YjRcdWIwOWMmbmJzcDsmcXVvdDtcdWJkOTlcdWM1ZWNcdWIxMjNcdWFlMzAmcXVvdDsgXHVjMmE0XHVkMGFjXHVjNzQ0IFx1Yzc3NFx1YzZhOVx1ZDU1OFx1YmE3NCZuYnNwO1x1YzViNFx1YjVhMFx1ZDU1YyBcdWFjMmZcdWMyMThcdWM3NTggXHViYjM4XHVjNzkwXHViM2M0IFx1YjJlOCAxXHVjZDA4XHViOWNjXHVjNWQwIFx1ZDBjMFx1Yzc3NFx1ZDU1MSBcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHViOWNjXHVjNTdkIFx1ZDU1Y1x1YzJlMFx1Yzc3NFx1YWMwMCAmcXVvdDtiYW5hJnF1b3Q7XHViOTdjIFx1YmNmNVx1YzBhY1x1ZDU1YyBcdWMwYzFcdWQwZGNcdWM1ZDBcdWMxMWMmbmJzcDsmcXVvdDtiYW5hbmEmcXVvdDtcdWI5N2MgXHVkMGMwXHVjNzc0XHVkNTUxXHVkNTVjXHViMmU0XHViYTc0LCZxdW90O2JhbmEmcXVvdDsgXHViZDk5XHVjNWVjXHViMTIzXHVhZTMwIDFcdWNkMDgsICYjMzk7biYjMzk7XHVjNzg1XHViODI1LCAmIzM5O2EmIzM5O1x1Yzc4NVx1YjgyNVx1ZDU3NFx1YzExYyBcdWNkMWQgM1x1Y2QwOFx1YWMwMCBcdWFjNzhcdWI5YjBcdWIyZTQuIFx1ZDU1Y1x1YzJlMFx1Yzc3NFx1YWMwMCBcdWQwNzRcdWI5YmRcdWJjZjRcdWI0ZGNcdWM1ZDAgXHVjODAwXHVjN2E1XHVkNTVjJm5ic3A7cFx1Yjk3YyBcdWM1NGNcdWFjZTAgXHVjNzg4XHVjNzQ0XHViNTRjIHNcdWI5N2MgXHVjNzg1XHViODI1XHVkNTU4XHViMjk0XHViMzcwIFx1YWM3OFx1YjlhY1x1YjI5NCBcdWNkNWNcdWMxOGMgXHVjMmRjXHVhYzA0XHVjNzQ0IFx1YWNjNFx1YzBiMFx1ZDU3NFx1YmNmNFx1Yzc5MCE8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YmM4OFx1YzlmOCBcdWM5MDQgXHVjNzg1XHViODI1XHVjNzNjXHViODVjXHViMjk0IFx1YzgxNVx1YzIxOCZuYnNwO1QoVCZsdDs9MjUpXHViOTdjIFx1ZDE0Y1x1YzJhNFx1ZDJiOCZuYnNwO1x1Y2YwMFx1Yzc3NFx1YzJhNFx1Yjg1YyBcdWM3ODVcdWI4MjVcdWJjMWJcdWIyOTRcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjhcdWNmMDBcdWM3NzRcdWMyYTRcdWIyOTQgXHVkNTVjIFx1YzkwNFx1YzVkMCAyXHVhYzFjXHVjNzU4IFx1YmIzOFx1Yzc5MFx1YzVmNCBzXHVjNjQwIHBcdWFjMDAmbmJzcDtcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0IFx1Yzc4NVx1YjgyNVx1YjQxOFx1YmE3MCZuYnNwOyBcdWQ1NWNcdWMyZTBcdWM3NzRcdWIyOTQgcFx1Yjk3YyBcdWJjZjVcdWMwYWNcdWQ1NThcdWM1ZWMgc1x1Yjk3YyBcdWI5Y2NcdWI0ZTRcdWM1YjQgXHViMGI0XHViMjk0Jm5ic3A7XHVhYzgzXHVjNzQ0IFx1YmFhOVx1ZDQ1Y1x1Yjg1YyBcdWQ1NWNcdWIyZTQuJm5ic3A7c1x1Yzc1OCZuYnNwO1x1Y2Q1Y1x1YjMwMCBcdWFlMzhcdWM3NzQmbmJzcDsxMDAwMFx1Yzc3NFx1YWNlMCwgcFx1Yzc1OCBcdWNkNWNcdWIzMDAgXHVhZTM4XHVjNzc0XHViMjk0IDEwMFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEmbmJzcDtcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjlkZVx1YjI5NCBcdWQ1NWNcdWMyZTBcdWM3NzRcdWFjMDAgcFx1Yjk3YyBcdWM3NzRcdWM2YTlcdWQ1NThcdWM1ZWMgc1x1Yjk3YyBcdWQwYzBcdWM3NzRcdWQ1NTEgXHVkNTYwXHViNTRjIFx1YWM3OFx1YjlhY1x1YjI5NCBcdWNkNWNcdWMxOGMgXHVjMmRjXHVhYzA0KFx1Y2QwOCZuYnNwO1x1YjJlOFx1YzcwNClcdWM3NDQgXHVjZDljXHViODI1XHVkNTU4XHViNzdjITxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjExMDA4IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiVHlwaW5nIiwiZGVzY3JpcHRpb24iOiI8cD5DYXRoeSZyc3F1bztzIHR5cGluZyBzcGVlZCBpcyBub3QgZmFzdCwgaG93ZXZlciwgaXQgaXMgdmVyeSBzdGVhZHkuIFNoZSBzdHJva2VzIHRoZSBrZXlib2FyZCBleGFjdCBvbmNlIHBlciBzZWNvbmQsIGFuZCBzaGUgYWx3YXlzIHByZXNzZXMgdGhlIGtleXMgY29ycmVjdGx5LiBXaXRob3V0IGludGVyZmVyaW5nLCBDYXRoeSBoYXMgdG8gc3BlbmQgbiBzZWNvbmRzIHRvIHR5cGUgYSBzdHJpbmcgcyBvZiBuIGNoYXJhY3RlcnMuIEluIG9yZGVyIHRvIHJlZHVjZSB0aGUgdGltZSBzcGVudCBmb3IgdHlwaW5nLCBDYXRoeSBjb3BpZWQgYSBzdHJpbmcgcCB0byB0aGUgY2xpcGJvYXJkLiBUaGVyZWZvcmUsIHNoZSBjYW4gdXNlIHRoZSAmbGRxdW87cGFzdGUmcmRxdW87IGZ1bmN0aW9uIHRvIGlucHV0IG1hbnkgY2hhcmFjdGVycy4gQXNzdW1lIHRoYXQgcGFzdGluZyBwIGFsc28gdGFrZXMgb25seSBvbmUga2V5Ym9hcmQgc3Ryb2tlIGZvciBDYXRoeS4gSWYgQ2F0aHkgY29waWVkIGJhbmEgYmVmb3JlIHR5cGluZyBiYW5hbmEsIHRoZW4gQ2F0aHkgY2FuIGZpbmlzaCBpdCBpbiAzIHNlY29uZHM6IHBhc3RpbmcgYmFuYSwgdGhlbiBwcmVzc2luZyBuLCB0aGVuIHByZXNzaW5nIGEuIFBsZWFzZSB3cml0ZSBhIHByb2dyYW0gdG8gY29tcHV0ZSB0aGUgbWluaW11bSB0aW1lIHJlcXVpcmVkIGZvciBDYXRoeSB0byB0eXBlIGEgc3RyaW5nIHMgd2hlbiBzaGUgY29waWVkIHAgdG8gdGhlIGNsaXBib2FyZC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIHRoZSBpbnB1dCBjb250YWlucyBhbiBpbnRlZ2VyIFQsIFQgJmxlOyAyNSwgaW5kaWNhdGluZyB0aGUgbnVtYmVyIG9mIHRlc3QgY2FzZXMuIEVhY2ggdGVzdCBjYXNlIGhhcyBleGFjdGx5IG9uZSBsaW5lIGNvbnRhaW5pbmcgdHdvIHN0cmluZ3MgcyBhbmQgcCBzZXBhcmF0ZWQgYnkgYmxhbmtzLiBDYXRoeSBpcyBnb2luZyB0byB0eXBlIHMgd2l0aCBwIGNvcGllZCB0byB0aGUgY2xpcGJvYXJkLiBUaGUgbGVuZ3RoIG9mIHMgaXMgYXQgbW9zdCAxMDAwMCwgYW5kIHRoZSBsZW5ndGggb2YgcCBpcyBhdCBtb3N0IDEwMC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2UsIG91dHB1dCB0aGUgbWluaW11bSB0aW1lIChpbiBzZWNvbmRzKSBmb3IgQ2F0aHkgdG8gdHlwZSBzIHdpdGggcCBjb3BpZWQgdG8gdGhlIGNsaXBib2FyZC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=