시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 100 64 45 60.811%

문제

선영이는 계산기와 컴퓨터에 매우 의존하는 학생이다. 따라서, 암산을 전혀 하지 못한다. (이건 사실이다)

하지만 선영이만 이런 것이 아니다. 상근이, 창영이, 종수 할아버지, 등등 많은 선영이의 친구도 간단한 계산을 전자기기의 도움 없이는 하지 못한다.

이런 까닭으로 어리석은 친구들이 이르고자 할 바가 있어도 마침내 제 뜻을 실어 펴지 못하는 사람이 많으니라. 나 선영이는 내 이를 위하여 가엾이 여거 새로 집합론을 기반으로 한 덧셈을 방법을 만들었다. 사람마다 하여 쉬이 익혀 날로 씀에 편안케 하고자 할 따름이니라.

이 방법은 음이 아닌 정수의 덧셈을 할 수 있다. 먼저, 음이 아닌 정수를 아래와 같이 집합으로 표현해야 한다.

0은 빈 집합 {} 이다.

0보다 큰 수 n은, n보다 작은 수를 모두 포함하는 집합으로 나타낸다.

아래 예는 0부터 3까지를 선영이의 방법으로 나타낸 것이다.

0 => {}
1 => {{}}
2 => {{},{{}}}
3 => {{},{{}},{{},{{}}}}

집합의 원소의 개수는 그 수가 나타내는 값과 같다. 집합에 포함되어 있는 원소는 순서가 없다. 선영이는 사람들이 혼란스러워 하는 것을 막기 위해서 원소의 순서는 항상 그 원소(집합)의 크기가 증가하는 순서대로 쓴다고 정했다.

선영이의 집합 숫자 표기법으로 나타낸 두 수가 주어졌을 때, 두 수의 합을 다시 집합 숫자 표기법으로 나타내는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 두 줄로 이루어져 있고, 집합 숫자 표기법으로 나타낸 수가 주어진다. 두 수의 합은 항상 15보다 작거나 같다.

출력

각 테스트 케이스에 대해서 입력으로 주어진 두 수의 합을 집합 숫자 표기법으로 출력한다.

예제 입력 1

3
{}
{}
{{}}
{{},{{}}}
{{},{{}},{{},{{}}}}
{{}}

예제 출력 1

{}
{{},{{}},{{},{{}}}}
{{},{{}},{{},{{}}},{{},{{}},{{},{{}}}}}
W3sicHJvYmxlbV9pZCI6IjQ4NDgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM5ZDFcdWQ1NjkgXHVjMjJiXHVjNzkwIFx1ZDQ1Y1x1YWUzMFx1YmM5NSIsImRlc2NyaXB0aW9uIjoiPHA+XHVjMTIwXHVjNjAxXHVjNzc0XHViMjk0IFx1YWNjNFx1YzBiMFx1YWUzMFx1YzY0MCBcdWNlZjRcdWQ0ZThcdWQxMzBcdWM1ZDAgXHViOWU0XHVjNmIwIFx1Yzc1OFx1Yzg3NFx1ZDU1OFx1YjI5NCBcdWQ1NTlcdWMwZGRcdWM3NzRcdWIyZTQuIFx1YjUzMFx1Yjc3Y1x1YzExYywgXHVjNTU0XHVjMGIwXHVjNzQ0IFx1YzgwNFx1ZDYwMCBcdWQ1NThcdWM5YzAgXHViYWJiXHVkNTVjXHViMmU0LiAoXHVjNzc0XHVhYzc0IFx1YzBhY1x1YzJlNFx1Yzc3NFx1YjJlNCk8XC9wPlxyXG5cclxuPHA+XHVkNTU4XHVjOWMwXHViOWNjIFx1YzEyMFx1YzYwMVx1Yzc3NFx1YjljYyBcdWM3NzRcdWI3ZjAgXHVhYzgzXHVjNzc0IFx1YzU0NFx1YjJjOFx1YjJlNC4gXHVjMGMxXHVhZGZjXHVjNzc0LCBcdWNjM2RcdWM2MDFcdWM3NzQsIFx1Yzg4NVx1YzIxOCBcdWQ1NjBcdWM1NDRcdWJjODRcdWM5YzAsIFx1YjRmMVx1YjRmMSBcdWI5Y2VcdWM3NDAgXHVjMTIwXHVjNjAxXHVjNzc0XHVjNzU4IFx1Y2U1Y1x1YWQ2Y1x1YjNjNCBcdWFjMDRcdWIyZThcdWQ1NWMgXHVhY2M0XHVjMGIwXHVjNzQ0IFx1YzgwNFx1Yzc5MFx1YWUzMFx1YWUzMFx1Yzc1OCBcdWIzYzRcdWM2YzAgXHVjNWM2XHVjNzc0XHViMjk0IFx1ZDU1OFx1YzljMCBcdWJhYmJcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc3NFx1YjdmMCBcdWFlNGNcdWIyZWRcdWM3M2NcdWI4NWMgXHVjNWI0XHViOWFjXHVjMTFkXHVjNzQwIFx1Y2U1Y1x1YWQ2Y1x1YjRlNFx1Yzc3NCBcdWM3NzRcdWI5NzRcdWFjZTBcdWM3OTAgXHVkNTYwIFx1YmMxNFx1YWMwMCBcdWM3ODhcdWM1YjRcdWIzYzQgXHViOWM4XHVjZTY4XHViMGI0IFx1YzgxYyBcdWI3M2JcdWM3NDQgXHVjMmU0XHVjNWI0IFx1ZDNiNFx1YzljMCBcdWJhYmJcdWQ1NThcdWIyOTQgXHVjMGFjXHViNzhjXHVjNzc0IFx1YjljZVx1YzczY1x1YjJjOFx1Yjc3Yy4gXHViMDk4IFx1YzEyMFx1YzYwMVx1Yzc3NFx1YjI5NCBcdWIwYjQgXHVjNzc0XHViOTdjIFx1YzcwNFx1ZDU1OFx1YzVlYyBcdWFjMDBcdWM1ZmVcdWM3NzQgXHVjNWVjXHVhYzcwIFx1YzBjOFx1Yjg1YyBcdWM5ZDFcdWQ1NjlcdWI4NjBcdWM3NDQgXHVhZTMwXHViYzE4XHVjNzNjXHViODVjIFx1ZDU1YyBcdWIzNjdcdWMxNDhcdWM3NDQgXHViYzI5XHViYzk1XHVjNzQ0IFx1YjljY1x1YjRlNFx1YzVjOFx1YjJlNC4gXHVjMGFjXHViNzhjXHViOWM4XHViMmU0IFx1ZDU1OFx1YzVlYyBcdWMyNmNcdWM3NzQgXHVjNzc1XHVkNjAwIFx1YjBhMFx1Yjg1YyBcdWM1MDBcdWM1ZDAgXHVkM2I4XHVjNTQ4XHVjZjAwIFx1ZDU1OFx1YWNlMFx1Yzc5MCBcdWQ1NjAgXHViNTMwXHViOTg0XHVjNzc0XHViMmM4XHViNzdjLjxcL3A+XHJcblxyXG48cD5cdWM3NzQgXHViYzI5XHViYzk1XHVjNzQwIFx1Yzc0Y1x1Yzc3NCBcdWM1NDRcdWIyY2MgXHVjODE1XHVjMjE4XHVjNzU4IFx1YjM2N1x1YzE0OFx1Yzc0NCBcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHViYTNjXHVjODAwLCBcdWM3NGNcdWM3NzQgXHVjNTQ0XHViMmNjIFx1YzgxNVx1YzIxOFx1Yjk3YyBcdWM1NDRcdWI3OThcdWM2NDAgXHVhYzE5XHVjNzc0IFx1YzlkMVx1ZDU2OVx1YzczY1x1Yjg1YyBcdWQ0NWNcdWQ2MDRcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD4wXHVjNzQwIFx1YmU0OCBcdWM5ZDFcdWQ1Njkge30gXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD4wXHViY2Y0XHViMmU0IFx1ZDA3MCBcdWMyMTggblx1Yzc0MCwgblx1YmNmNFx1YjJlNCBcdWM3OTFcdWM3NDAgXHVjMjE4XHViOTdjIFx1YmFhOFx1YjQ1MCBcdWQzZWNcdWQ1NjhcdWQ1NThcdWIyOTQgXHVjOWQxXHVkNTY5XHVjNzNjXHViODVjIFx1YjA5OFx1ZDBjMFx1YjBiOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNTQ0XHViNzk4IFx1YzYwOFx1YjI5NCAwXHViZDgwXHVkMTMwIDNcdWFlNGNcdWM5YzBcdWI5N2MgXHVjMTIwXHVjNjAxXHVjNzc0XHVjNzU4IFx1YmMyOVx1YmM5NVx1YzczY1x1Yjg1YyBcdWIwOThcdWQwYzBcdWIwYjggXHVhYzgzXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD4wID0mZ3Q7IHt9PGJyIFwvPlxyXG4xID0mZ3Q7IHt7fX08YnIgXC8+XHJcbjIgPSZndDsge3t9LHt7fX19PGJyIFwvPlxyXG4zID0mZ3Q7IHt7fSx7e319LHt7fSx7e319fX08XC9wPlxyXG5cclxuPHA+XHVjOWQxXHVkNTY5XHVjNzU4IFx1YzZkMFx1YzE4Y1x1Yzc1OCBcdWFjMWNcdWMyMThcdWIyOTQgXHVhZGY4IFx1YzIxOFx1YWMwMCBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgXHVhYzEyXHVhY2ZjIFx1YWMxOVx1YjJlNC4gXHVjOWQxXHVkNTY5XHVjNWQwIFx1ZDNlY1x1ZDU2OFx1YjQxOFx1YzViNCBcdWM3ODhcdWIyOTQgXHVjNmQwXHVjMThjXHViMjk0IFx1YzIxY1x1YzExY1x1YWMwMCBcdWM1YzZcdWIyZTQuIFx1YzEyMFx1YzYwMVx1Yzc3NFx1YjI5NCBcdWMwYWNcdWI3OGNcdWI0ZTRcdWM3NzQgXHVkNjNjXHViNzgwXHVjMmE0XHViN2VjXHVjNmNjIFx1ZDU1OFx1YjI5NCBcdWFjODNcdWM3NDQgXHViOWM5XHVhZTMwIFx1YzcwNFx1ZDU3NFx1YzExYyBcdWM2ZDBcdWMxOGNcdWM3NTggXHVjMjFjXHVjMTFjXHViMjk0IFx1ZDU2ZFx1YzBjMSBcdWFkZjggXHVjNmQwXHVjMThjKFx1YzlkMVx1ZDU2OSlcdWM3NTggXHVkMDZjXHVhZTMwXHVhYzAwIFx1Yzk5ZFx1YWMwMFx1ZDU1OFx1YjI5NCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVjNGY0XHViMmU0XHVhY2UwIFx1YzgxNVx1ZDU4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMTIwXHVjNjAxXHVjNzc0XHVjNzU4IFx1YzlkMVx1ZDU2OSBcdWMyMmJcdWM3OTAgXHVkNDVjXHVhZTMwXHViYzk1XHVjNzNjXHViODVjIFx1YjA5OFx1ZDBjMFx1YjBiOCBcdWI0NTAgXHVjMjE4XHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YjQ1MCBcdWMyMThcdWM3NTggXHVkNTY5XHVjNzQ0IFx1YjJlNFx1YzJkYyBcdWM5ZDFcdWQ1NjkgXHVjMjJiXHVjNzkwIFx1ZDQ1Y1x1YWUzMFx1YmM5NVx1YzczY1x1Yjg1YyBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWFjMWNcdWMyMThcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWI0NTAgXHVjOTA0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWFjZTAsIFx1YzlkMVx1ZDU2OSBcdWMyMmJcdWM3OTAgXHVkNDVjXHVhZTMwXHViYzk1XHVjNzNjXHViODVjIFx1YjA5OFx1ZDBjMFx1YjBiOCBcdWMyMThcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWI0NTAgXHVjMjE4XHVjNzU4IFx1ZDU2OVx1Yzc0MCBcdWQ1NmRcdWMwYzEgMTVcdWJjZjRcdWIyZTQgXHVjNzkxXHVhYzcwXHViMDk4IFx1YWMxOVx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMgXHVjNzg1XHViODI1XHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljNCBcdWI0NTAgXHVjMjE4XHVjNzU4IFx1ZDU2OVx1Yzc0NCBcdWM5ZDFcdWQ1NjkgXHVjMjJiXHVjNzkwIFx1ZDQ1Y1x1YWUzMFx1YmM5NVx1YzczY1x1Yjg1YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNDg0OCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkVsZW1lbnRhcnkgQWRkaXRpb25zIiwiZGVzY3JpcHRpb24iOiI8cD5JbiB0b2RheSYjMzk7cyBlbnZpcm9ubWVudCwgc3R1ZGVudHMgcmVseSBvbiBjYWxjdWxhdG9ycyBhbmQgY29tcHV0ZXJzIHRvIHBlcmZvcm0gc2ltcGxlIGFyaXRobWV0aWMgdG9vIG11Y2guIFNhZGx5LCBpdCBpcyBub3QgdW5jb21tb24gdG8gc2VlIHVuaXZlcnNpdHkgc3R1ZGVudHMgd2hvIGNhbm5vdCBkbyBzaW1wbGUgYXJpdGhtZXRpYyB3aXRob3V0IGVsZWN0cm9uaWMgYWlkcy4gUHJvZmVzc29yIFBlYW5vIGhhcyBoYWQgZW5vdWdoLiBIZSBoYXMgZGVjaWRlZCB0byB0YWtlIHRoZSBtYXR0ZXIgaW50byBoaXMgb3duIGhhbmRzIGFuZCBmb3JjZSBoaXMgc3R1ZGVudHMgdG8gYmVjb21lIHByb2ZpY2llbnQgaW4gdGhlIG1vc3QgYmFzaWMgYXJpdGhtZXRpYyBza2lsbDogYWRkaXRpb24gb2Ygbm9uJm1pbnVzO25lZ2F0aXZlIGludGVnZXJzLiBTaW5jZSB0aGUgc3R1ZGVudHMgZG8gbm90IGhhdmUgYSBnb29kIGZvdW5kYXRpb24gaW4gdGhpcyBza2lsbCwgaGUgZGVjaWRlZCB0byBnbyBiYWNrIHRvIHRoZSBiYXNpY3MgYW5kIHJlcHJlc2VudCBub24mbWludXM7bmVnYXRpdmUgaW50ZWdlcnMgd2l0aCBzZXQgdGhlb3J5LjxcL3A+XHJcblxyXG48cD5UaGUgbm9uJm1pbnVzO25lZ2F0aXZlIGludGVnZXJzIGFyZSByZXByZXNlbnRlZCBieSB0aGUgZm9sbG93aW5nIHNldHM6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+MCBpcyByZXByZXNlbnRlZCBieSB0aGUgZW1wdHkgc2V0IHt9LjxcL2xpPlxyXG5cdDxsaT5Gb3IgYW55IG51bWJlciBuICZndDsgMCwgbiBpcyByZXByZXNlbnRlZCBieSBhIHNldCBjb250YWluaW5nIHRoZSByZXByZXNlbnRhdGlvbnMgb2YgYWxsIG5vbiZtaW51cztuZWdhdGl2ZSBpbnRlZ2VycyBzbWFsbGVyIHRoYW4gbi4mbmJzcDs8XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5Gb3IgZXhhbXBsZSwgdGhlIGZpcnN0IDQgbm9uJm1pbnVzO25lZ2F0aXZlIGludGVnZXJzIGFyZSByZXByZXNlbnRlZCBieTo8XC9wPlxyXG5cclxuPHA+MCA9Jmd0OyB7fTxiciBcLz5cclxuMSA9Jmd0OyB7e319PGJyIFwvPlxyXG4yID0mZ3Q7IHt7fSx7e319fTxiciBcLz5cclxuMyA9Jmd0OyB7e30se3t9fSx7e30se3t9fX19PFwvcD5cclxuXHJcbjxwPmFuZCBzbyBvbi4gTm90aWNlIHRoYXQgdGhlIGNhcmRpbmFsaXR5IChzaXplKSBvZiB0aGUgc2V0IGlzIGV4YWN0bHkgdGhlIGludGVnZXIgaXQgcmVwcmVzZW50cy4gQWx0aG91Z2ggdGhlIGVsZW1lbnRzIG9mIGEgc2V0IGFyZSBnZW5lcmFsbHkgdW5vcmRlcmVkLCBQcm9mZXNzb3IgUGVhbm8gcmVxdWlyZXMgdGhhdCB0aGUgZWxlbWVudHMgb2YgYSBzZXQgYmUgb3JkZXJlZCBpbiBpbmNyZWFzaW5nIGNhcmRpbmFsaXR5IHRvIG1ha2UgdGhlIGFzc2lnbm1lbnRzIGVhc2llciB0byBncmFkZS4gQXMgYW4gYWRkZWQgYWR2YW50YWdlLCBQcm9mZXNzb3IgUGVhbm8gaXMgc3VyZSB0aGF0IHRoZXJlIGFyZSBubyBjYWxjdWxhdG9ycyBvciBjb21wdXRlciBwcm9ncmFtcyB0aGF0IGNhbiBkZWFsIHdpdGggbnVtYmVycyB3cml0dGVuIGluIHRoaXMgbm90YXRpb24uPFwvcD5cclxuXHJcbjxwPk5vdCBzdXJwcmlzaW5nbHksIG1hbnkgc3R1ZGVudHMgY2Fubm90IGNvcGUgd2l0aCB0aGlzIGJhc2ljIHRhc2sgYW5kIHdpbGwgZmFpbCB0aGUgY291cnNlIGlmIHRoZXkgZG8gbm90IGdldCBoZWxwIHNvb24uIEl0IGlzIHVwIHRvIHlvdSwgYW4gZW50ZXJwcmlzaW5nIGNvbXB1dGVyIHNjaWVuY2Ugc3R1ZGVudCwgdG8gaGVscCB0aGVtLiBZb3UgaGF2ZSBkZWNpZGVkIHRvIHdyaXRlIGEgY29tcHV0ZXIgcHJvZ3JhbSwgY29kZW5hbWVkIEF4aW9tYXRpYyBDaGVhdGluZyBNYWNoaW5lIChBQ00pLCB0byBzZWxsIHRvIHRoZSBzdHVkZW50cyBhbmQgaGVscCB0aGVtIHBlcmZvcm0gdGhlIGFkZGl0aW9ucyB0byBwYXNzIHRoZSBjb3Vyc2UuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiB0aGUgaW5wdXQgY29udGFpbnMgYSBwb3NpdGl2ZSBpbnRlZ2VyIGdpdmluZyB0aGUgbnVtYmVyIG9mIGNhc2VzIHRvIGZvbGxvdy4gRm9yIGVhY2ggY2FzZSwgdGhlcmUgYXJlIHR3byBsaW5lcyBvZiBpbnB1dCBlYWNoIGNvbnRhaW5pbmcgYSBub24mbWludXM7bmVnYXRpdmUgaW50ZWdlciByZXByZXNlbnRlZCBpbiBzZXQgbm90YXRpb24uIEVhY2ggbGluZSBjb250YWlucyBvbmx5IHRoZSBjaGFyYWN0ZXJzICYjMzk7eyYjMzk7LCAmIzM5O30mIzM5OywgYW5kICYjMzk7LCYjMzk7LiBUaGUgc3VtIG9mIHRoZSB0d28gZ2l2ZW4gaW50ZWdlcnMgd2lsbCBiZSBhdCBtb3N0IDE1LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHRlc3QgY2FzZSwgb3V0cHV0IHRoZSBzdW0gb2YgdGhlIHR3byBpbnB1dCBpbnRlZ2VycyBpbiB0aGUgc2V0IG5vdGF0aW9uIGRlc2NyaWJlZCBhYm92ZS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=