시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 231 126 115 60.526%

문제

만약 단어 A의 알파벳 순서를 바꿔서 단어 B를 만들 수 있다면, 두 단어는 애너그램이라고 한다. 예를 들어, occurs는 succor의 애너그램이지만, dear는 dared의 애너그램이 아니다. 영어에서 가장 유명한 애너그램은 dog와 god이다.

두 단어의 애너그램 거리란, 두 단어가 애너그램이 되기 위해서 지워야하는 단어의 최소 개수이다. 예를 들어, sleep과 leap이 주어졌다면, sleep에서 2개, leap에서 1개를 지운다면 두 단어는 애너그램 관계가 된다. 따라서, sleep과 leap의 애너그램 거리는 3이다. 서로 공통된 알파벳이 없는 dog와 cat같은 경우에는 모든 단어를 지워야 하기 때문에, 애너그램 거리가 6이다.

두 단어가 주어졌을 때, 두 단어의 애너그램 거리를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 N이 주어진다. N은 60,000보다 작거나 같은 자연수이다. 각 테스트 케이스는 두 줄로 이루어져 있고, 한 줄에 단어가 하나씩 주어진다.

단어의 길이는 0일 수도 있고, 알파벳 소문자로만 이루어져 있다. 단어는 실제로 영어 사전에 있는 단어만 주어지며, 영어 사전에서 가장 긴 단어는 pneumonoultramicroscopicsilicovolcanoconiosis이다.

출력

각 테스트 케이스에 대해서 케이스 번호와 입력으로 주어진 두 단어의 애너그램 거리를 출력한다.

예제 입력 1

4
crocus
succor
dares
seared
empty

smell
lemon

예제 출력 1

Case #1: 0
Case #2: 1
Case #3: 5
Case #4: 4
W3sicHJvYmxlbV9pZCI6IjM3NzgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM1NjBcdWIxMDhcdWFkZjhcdWI3YTggXHVhYzcwXHViOWFjIiwiZGVzY3JpcHRpb24iOiI8cD5cclxuXHRcdWI5Y2NcdWM1N2QgXHViMmU4XHVjNWI0IEFcdWM3NTggXHVjNTRjXHVkMzBjXHViY2IzIFx1YzIxY1x1YzExY1x1Yjk3YyBcdWJjMTRcdWFmZDRcdWMxMWMgXHViMmU4XHVjNWI0IEJcdWI5N2MgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM3ODhcdWIyZTRcdWJhNzQsIFx1YjQ1MCBcdWIyZThcdWM1YjRcdWIyOTQgXHVjNTYwXHViMTA4XHVhZGY4XHViN2E4XHVjNzc0XHViNzdjXHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgb2NjdXJzXHViMjk0IHN1Y2Nvclx1Yzc1OCBcdWM1NjBcdWIxMDhcdWFkZjhcdWI3YThcdWM3NzRcdWM5YzBcdWI5Y2MsIGRlYXJcdWIyOTQgZGFyZWRcdWM3NTggXHVjNTYwXHViMTA4XHVhZGY4XHViN2E4XHVjNzc0IFx1YzU0NFx1YjJjOFx1YjJlNC4gXHVjNjAxXHVjNWI0XHVjNWQwXHVjMTFjIFx1YWMwMFx1YzdhNSBcdWM3MjBcdWJhODVcdWQ1NWMgXHVjNTYwXHViMTA4XHVhZGY4XHViN2E4XHVjNzQwIGRvZ1x1YzY0MCBnb2RcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YjQ1MCBcdWIyZThcdWM1YjRcdWM3NTggXHVjNTYwXHViMTA4XHVhZGY4XHViN2E4IFx1YWM3MFx1YjlhY1x1Yjc4MCwgXHViNDUwIFx1YjJlOFx1YzViNFx1YWMwMCBcdWM1NjBcdWIxMDhcdWFkZjhcdWI3YThcdWM3NzQgXHViNDE4XHVhZTMwIFx1YzcwNFx1ZDU3NFx1YzExYyBcdWM5YzBcdWM2Y2NcdWM1N2NcdWQ1NThcdWIyOTQgXHViMmU4XHVjNWI0XHVjNzU4IFx1Y2Q1Y1x1YzE4YyBcdWFjMWNcdWMyMThcdWM3NzRcdWIyZTQuIFx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsIHNsZWVwXHVhY2ZjIGxlYXBcdWM3NzQgXHVjOGZjXHVjNWI0XHVjODRjXHViMmU0XHViYTc0LCBzbGVlcFx1YzVkMFx1YzExYyAyXHVhYzFjLCBsZWFwXHVjNWQwXHVjMTFjIDFcdWFjMWNcdWI5N2MgXHVjOWMwXHVjNmI0XHViMmU0XHViYTc0IFx1YjQ1MCBcdWIyZThcdWM1YjRcdWIyOTQgXHVjNTYwXHViMTA4XHVhZGY4XHViN2E4IFx1YWQwMFx1YWNjNFx1YWMwMCBcdWI0MWNcdWIyZTQuIFx1YjUzMFx1Yjc3Y1x1YzExYywgc2xlZXBcdWFjZmMgbGVhcFx1Yzc1OCBcdWM1NjBcdWIxMDhcdWFkZjhcdWI3YTggXHVhYzcwXHViOWFjXHViMjk0IDNcdWM3NzRcdWIyZTQuIFx1YzExY1x1Yjg1YyBcdWFjZjVcdWQxYjVcdWI0MWMgXHVjNTRjXHVkMzBjXHViY2IzXHVjNzc0IFx1YzVjNlx1YjI5NCBkb2dcdWM2NDAgY2F0XHVhYzE5XHVjNzQwIFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCBcdWJhYThcdWI0ZTAgXHViMmU4XHVjNWI0XHViOTdjIFx1YzljMFx1YzZjY1x1YzU3YyBcdWQ1NThcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwLCBcdWM1NjBcdWIxMDhcdWFkZjhcdWI3YTggXHVhYzcwXHViOWFjXHVhYzAwIDZcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YjQ1MCBcdWIyZThcdWM1YjRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHViNDUwIFx1YjJlOFx1YzViNFx1Yzc1OCBcdWM1NjBcdWIxMDhcdWFkZjhcdWI3YTggXHVhYzcwXHViOWFjXHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHJcblx0XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWMxY1x1YzIxOCBOXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gTlx1Yzc0MCA2MCwwMDBcdWJjZjRcdWIyZTQgXHVjNzkxXHVhYzcwXHViMDk4IFx1YWMxOVx1Yzc0MCBcdWM3OTBcdWM1ZjBcdWMyMThcdWM3NzRcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IFx1YjQ1MCBcdWM5MDRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YWNlMCwgXHVkNTVjIFx1YzkwNFx1YzVkMCBcdWIyZThcdWM1YjRcdWFjMDAgXHVkNTU4XHViMDk4XHVjNTI5IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHViMmU4XHVjNWI0XHVjNzU4IFx1YWUzOFx1Yzc3NFx1YjI5NCAwXHVjNzdjIFx1YzIxOFx1YjNjNCBcdWM3ODhcdWFjZTAsIFx1YzU0Y1x1ZDMwY1x1YmNiMyBcdWMxOGNcdWJiMzhcdWM3OTBcdWI4NWNcdWI5Y2MgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHViMmU4XHVjNWI0XHViMjk0IFx1YzJlNFx1YzgxY1x1Yjg1YyBcdWM2MDFcdWM1YjQgXHVjMGFjXHVjODA0XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWIyZThcdWM1YjRcdWI5Y2MgXHVjOGZjXHVjNWI0XHVjOWMwXHViYTcwLCBcdWM2MDFcdWM1YjQgXHVjMGFjXHVjODA0XHVjNWQwXHVjMTFjIFx1YWMwMFx1YzdhNSBcdWFlMzQgXHViMmU4XHVjNWI0XHViMjk0IHBuZXVtb25vdWx0cmFtaWNyb3Njb3BpY3NpbGljb3ZvbGNhbm9jb25pb3Npc1x1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cclxuXHRcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMgXHVjZjAwXHVjNzc0XHVjMmE0IFx1YmM4OFx1ZDYzOFx1YzY0MCBcdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0IFx1YjQ1MCBcdWIyZThcdWM1YjRcdWM3NTggXHVjNTYwXHViMTA4XHVhZGY4XHViN2E4IFx1YWM3MFx1YjlhY1x1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMzc3OCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkFuYWdyYW1tYXRpYyBEaXN0YW5jZSIsImRlc2NyaXB0aW9uIjoiPHA+VHdvIHdvcmRzIGFyZSBzYWlkIHRvIGJlIGFuYWdyYW1zIG9mIGVhY2ggb3RoZXIgaWYgdGhlIGxldHRlcnMgZnJvbSBvbmUgd29yZCBjYW4gYmUgcmVhcnJhbmdlZCB0byBmb3JtIHRoZSBvdGhlciB3b3JkLiBGb3IgZXhhbXBsZSwgb2NjdXJzIGlzIGFuIGFuYWdyYW0gb2Ygc3VjY29yOyBob3dldmVyLCBkZWFyIGlzIG5vdCBhbiBhbmFncmFtIG9mIGRhcmVkIChiZWNhdXNlIHRoZSBkIGFwcGVhcnMgdHdpY2UgaW4gZGFyZWQsIGJ1dCBvbmx5IG9uY2UgaW4gZGVhcikuIFRoZSBtb3N0IGZhbW91cyBhbmFncmFtIHBhaXIgKGluIEVuZ2xpc2gpIGlzIGRvZyBhbmQgZ29kLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgYW5hZ3JhbW1hdGljIGRpc3RhbmNlIGJldHdlZW4gYW55IHR3byB3b3JkcyBpcyB0aGUgbWluaW11bSBudW1iZXIgb2YgbGV0dGVycyB3aGljaCBtdXN0IGJlIHJlbW92ZWQgc28gdGhhdCB0aGUgcmVtYWluaW5nIHBvcnRpb25zIG9mIHRoZSB0d28gd29yZHMgYmVjb21lIGFuYWdyYW1zLiBGb3IgZXhhbXBsZSwgZ2l2ZW4gdGhlIHdvcmRzIHNsZWVwIGFuZCBsZWFwLCB3ZSBuZWVkIHRvIHJlbW92ZSBhIG1pbmltdW0gb2YgdGhyZWUgbGV0dGVycyAtLS0gdHdvIGZyb20gc2xlZXAgYW5kIG9uZSBmcm9tIGxlYXAgLS0tIGJlZm9yZSB3aGF0JiMzOTtzIGxlZnQgYXJlIGFuYWdyYW1zIG9mIGVhY2ggb3RoZXIgKGluIGVhY2ggY2FzZSwgbGVwKS4gV2l0aCB3b3JkcyBzdWNoIGFzIGRvZyBhbmQgY2F0LCB3aGVyZSB0aGUgdHdvIGhhdmUgYWJzb2x1dGVseSBubyBsZXR0ZXJzIGluIGNvbW1vbiwgdGhlIGFuYWdyYW1tYXRpYyBkaXN0YW5jZSBpcyBhbiBleHRyZW1lIChleHBsaWNpdGx5IDYpIHNpbmNlIGFsbCB0aGUgbGV0dGVycyBuZWVkIHRvIGJlIHJlbW92ZWQuIChIZXJlLCBhIHdvcmQgaXMgYWx3YXlzIGFuIGFuYWdyYW0gb2YgaXRzZWxmLikmbmJzcDs8XC9wPlxyXG5cclxuPHA+WW91IG11c3Qgd3JpdGUgYSBwcm9ncmFtIHRvIGNhbGN1bGF0ZSB0aGUgYW5hZ3JhbW1hdGljIGRpc3RhbmNlIGJldHdlZW4gYW55IHR3byBnaXZlbiB3b3Jkcy4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIHRoZSBpbnB1dCB3aWxsIGNvbnRhaW4gYSBwb3NpdGl2ZSBpbnRlZ2VyIHZhbHVlIE4gKGxlc3MgdGhhbiA2MCwwMDApIGluZGljYXRpbmcgdGhlIG51bWJlciBvZiBjYXNlcy4gRWFjaCBjYXNlIHdpbGwgY29uc2lzdCBvZiB0d28gd29yZHMsIHBvc3NpYmx5IGVtcHR5LCBlYWNoIGdpdmVuIG9uIGEgc2luZ2xlIGxpbmUgKGZvciBhIHRvdGFsIG9mIDJOIGFkZGl0aW9uYWwgbGluZXMpLiZuYnNwOzxcL3A+XHJcblxyXG48cD5BbHRob3VnaCB0aGV5IG1heSBoYXZlIHplcm8gbGVuZ3RoLCB0aGUgd29yZHMgYXJlIHNpbXBsZSAtLS0gdGhlIGxldHRlciBhcmUgYWxsIGxvd2VyY2FzZSBhbmQgYXJlIHRha2VuIGZyb20gdGhlIHVzdWFsIHR3ZW50eS1zaXggbGV0dGVyIEVuZ2xpc2ggYWxwaGFiZXQgKGFiY2RlZmdoaWprbG1ub3BxcnN0dXZ3eHl6KS4gVGhlIGxvbmdlc3Qgd29yZCBpcyBwbmV1bW9ub3VsdHJhbWljcm9zY29waWNzaWxpY292b2xjYW5vY29uaW9zaXMuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIG91dHB1dCBzaG91bGQgY29uc2lzdCBvZiB0aGUgY2FzZSBudW1iZXIgYW5kIHRoZSBhbmFncmFtbWF0aWMgZGlzdGFuY2UsIGZvcm1hdHRlZCBhcyBzaG93bi4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

ACM-ICPC > Regionals > Europe > Southeastern European Regional Contest > SEERC 2005 H번