시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 128 MB 111 10 2 2.632%

문제

어떤 날자가 팰린드롬이 되려면, "YearMMDD"형태로 썼을 때, 팰린드롬이어야 한다. 예를 들면, "1년 1월 1일"은 숫자로 나타내면 "10101"이기 때문에 팰린드롬이며, "1021년 12월 1일"도 숫자로 나타내면 "10211201"이기 때문에 팰린드롬이다.

날짜가 주어졌을 때, 그 날짜 다음에 나오는 팰린드롬 날짜를 찾는 프로그램을 작성하시오. 

이 문제에서 연도는 1보다 크거나 같고, 2147483647보다 작거나 같다. 또한, 윤년도 계산해야 하며, 윤년에 대한 정보는 2753번에서 찾을 수 있다.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 날짜가 일/월/연도 형태로 주어진다. 월과 일을 나타낼 때, 앞에 0이 있을 수도 있고 없을 수도 있다. 예를 들어, 2011년 7월 4일은 "04/07/2011", "4/07/2011", "4/7/2011", "04/7/2011"로 나타낼 수 있다.

출력

입력으로 주어진 날짜의 다음에 오는 팰린드롬 날짜를 일/월/연도 형태로 출력한다. 연도의 첫번째 숫자는 0이 되면 안되고, 월과 일은 두자리로 출력해야 한다. (1대신에 01, 2대신에 02) 항상 다음 팰린드롬 날짜가 존재하는 경우만 입력으로 주어진다.

예제 입력 1

3
1/1/1
12/11/1
01/06/138048967

예제 출력 1

01/02/1
11/12/1
31/08/138048984
W3sicHJvYmxlbV9pZCI6IjM3MTkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQzMzBcdWI5YjBcdWI0ZGNcdWI4NmMgXHViMGEwXHVjOWRjIiwiZGVzY3JpcHRpb24iOiI8cD5cclxuXHRcdWM1YjRcdWI1YTQgXHViMGEwXHVjNzkwXHVhYzAwIFx1ZDMzMFx1YjliMFx1YjRkY1x1Yjg2Y1x1Yzc3NCBcdWI0MThcdWI4MjRcdWJhNzQsICZxdW90O1llYXJNTUREJnF1b3Q7XHVkNjE1XHVkMGRjXHViODVjIFx1YzM3Y1x1Yzc0NCBcdWI1NGMsIFx1ZDMzMFx1YjliMFx1YjRkY1x1Yjg2Y1x1Yzc3NFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWJhNzQsICZxdW90OzFcdWIxNDQgMVx1YzZkNCAxXHVjNzdjJnF1b3Q7XHVjNzQwIFx1YzIyYlx1Yzc5MFx1Yjg1YyBcdWIwOThcdWQwYzBcdWIwYjRcdWJhNzQgJnF1b3Q7MTAxMDEmcXVvdDtcdWM3NzRcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwIFx1ZDMzMFx1YjliMFx1YjRkY1x1Yjg2Y1x1Yzc3NFx1YmE3MCwgJnF1b3Q7MTAyMVx1YjE0NCAxMlx1YzZkNCAxXHVjNzdjJnF1b3Q7XHViM2M0IFx1YzIyYlx1Yzc5MFx1Yjg1YyBcdWIwOThcdWQwYzBcdWIwYjRcdWJhNzQgJnF1b3Q7MTAyMTEyMDEmcXVvdDtcdWM3NzRcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwIFx1ZDMzMFx1YjliMFx1YjRkY1x1Yjg2Y1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHViMGEwXHVjOWRjXHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YWRmOCBcdWIwYTBcdWM5ZGMgXHViMmU0XHVjNzRjXHVjNWQwIFx1YjA5OFx1YzYyNFx1YjI5NCBcdWQzMzBcdWI5YjBcdWI0ZGNcdWI4NmMgXHViMGEwXHVjOWRjXHViOTdjIFx1Y2MzZVx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LiZuYnNwOzxcL3A+XHJcblxyXG48cD5cclxuXHRcdWM3NzQgXHViYjM4XHVjODFjXHVjNWQwXHVjMTFjIFx1YzVmMFx1YjNjNFx1YjI5NCAxXHViY2Y0XHViMmU0IFx1ZDA2Y1x1YWM3MFx1YjA5OCBcdWFjMTlcdWFjZTAsIDIxNDc0ODM2NDdcdWJjZjRcdWIyZTQgXHVjNzkxXHVhYzcwXHViMDk4IFx1YWMxOVx1YjJlNC4gXHViNjEwXHVkNTVjLCBcdWM3MjRcdWIxNDRcdWIzYzQgXHVhY2M0XHVjMGIwXHVkNTc0XHVjNTdjIFx1ZDU1OFx1YmE3MCwgXHVjNzI0XHViMTQ0XHVjNWQwIFx1YjMwMFx1ZDU1YyBcdWM4MTVcdWJjZjRcdWIyOTQgPGEgaHJlZj1cImh0dHA6XC9cL3d3dy5hY21pY3BjLm5ldFwvcHJvYmxlbVwvMjc1M1wiPjI3NTNcdWJjODg8XC9hPlx1YzVkMFx1YzExYyBcdWNjM2VcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlxyXG5cdFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWFjMWNcdWMyMTggVFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IFx1ZDU1YyBcdWM5MDRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YWNlMCwgXHViMGEwXHVjOWRjXHVhYzAwIFx1Yzc3Y1wvXHVjNmQ0XC9cdWM1ZjBcdWIzYzQgXHVkNjE1XHVkMGRjXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNmQ0XHVhY2ZjIFx1Yzc3Y1x1Yzc0NCBcdWIwOThcdWQwYzBcdWIwYmMgXHViNTRjLCBcdWM1NWVcdWM1ZDAgMFx1Yzc3NCBcdWM3ODhcdWM3NDQgXHVjMjE4XHViM2M0IFx1Yzc4OFx1YWNlMCBcdWM1YzZcdWM3NDQgXHVjMjE4XHViM2M0IFx1Yzc4OFx1YjJlNC4gXHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgMjAxMVx1YjE0NCA3XHVjNmQ0IDRcdWM3N2NcdWM3NDAgJnF1b3Q7MDRcLzA3XC8yMDExJnF1b3Q7LCAmcXVvdDs0XC8wN1wvMjAxMSZxdW90OywgJnF1b3Q7NFwvN1wvMjAxMSZxdW90OywgJnF1b3Q7MDRcLzdcLzIwMTEmcXVvdDtcdWI4NWMgXHViMDk4XHVkMGMwXHViMGJjIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHJcblx0XHVjNzg1XHViODI1XHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljNCBcdWIwYTBcdWM5ZGNcdWM3NTggXHViMmU0XHVjNzRjXHVjNWQwIFx1YzYyNFx1YjI5NCBcdWQzMzBcdWI5YjBcdWI0ZGNcdWI4NmMgXHViMGEwXHVjOWRjXHViOTdjIFx1Yzc3Y1wvXHVjNmQ0XC9cdWM1ZjBcdWIzYzQgXHVkNjE1XHVkMGRjXHViODVjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVjNWYwXHViM2M0XHVjNzU4IFx1Y2NhYlx1YmM4OFx1YzlmOCBcdWMyMmJcdWM3OTBcdWIyOTQgMFx1Yzc3NCBcdWI0MThcdWJhNzQgXHVjNTQ4XHViNDE4XHVhY2UwLCBcdWM2ZDRcdWFjZmMgXHVjNzdjXHVjNzQwIFx1YjQ1MFx1Yzc5MFx1YjlhY1x1Yjg1YyBcdWNkOWNcdWI4MjVcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LiAoMVx1YjMwMFx1YzJlMFx1YzVkMCAwMSwgMlx1YjMwMFx1YzJlMFx1YzVkMCAwMikgXHVkNTZkXHVjMGMxIFx1YjJlNFx1Yzc0YyBcdWQzMzBcdWI5YjBcdWI0ZGNcdWI4NmMgXHViMGEwXHVjOWRjXHVhYzAwIFx1Yzg3NFx1YzdhY1x1ZDU1OFx1YjI5NCBcdWFjYmRcdWM2YjBcdWI5Y2MgXHVjNzg1XHViODI1XHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIzNzE5IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiUGFsaW5kcm9taWMgRGF0ZXMiLCJkZXNjcmlwdGlvbiI6IjxwPkEgZGF0ZSBpcyBzYWlkIHRvIGJlIHBhbGluZHJvbWljIGlmLCB3aGVuIHdyaXR0ZW4gaW4gdGhlIGZvcm0gJmxkcXVvO1llYXJNTUREJnJkcXVvOywgdGhlIHJlc3VsdCBpcyBhICZuYnNwO3BhbGluZHJvbWUgKGEgbnVtYmVyIHRoYXQgaGFzIHRoZSBzYW1lIHZhbHVlIHJlZ2FyZGxlc3MgaWYgd2UgcmVhZCBpdCBsZWZ0LXRvLXJpZ2h0IG9yIHJpZ2h0LXRvLWxlZnQpLiBGb3IgZXhhbXBsZSwgdGhlIGRhdGUgJmxkcXVvO0phbnVhcnkgMXN0LCAxJnJkcXVvOyBpcyBwYWxpbmRyb21pYyBzaW5jZSBpdCB3b3VsZCBiZSB3cml0dGVuIGFzICZsZHF1bzsxMDEwMSZyZHF1bzs7Jm5ic3A7JmxkcXVvO0RlY2VtYmVyIDFzdCwgMTAyMSZyZHF1bzsgaXMgcGFsaW5kcm9taWMgdG9vLCBzaW5jZSBpdCB3b3VsZCBiZSB3cml0dGVuIGFzICZsZHF1bzsxMDIxMTIwMSZyZHF1bzsuPFwvcD5cclxuXHJcbjxwPkdpdmVuIGEgZGF0ZSwgeW91IGFyZSByZXF1aXJlZCB0byBmaW5kIHRoZSBuZXh0IHZhbGlkIGRhdGUgKGluIGNocm9ub2xvZ2ljYWwgb3JkZXIpIHRoYXQgaXMgJm5ic3A7cGFsaW5kcm9taWMgKGFjY29yZGluZyB0byB0aGUgZGVmaW5pdGlvbiBvZiAmbGRxdW87cGFsaW5kcm9taWMgZGF0ZSZyZHF1bzsgdGhhdCB3YXMgZ2l2ZW4gaW4gdGhlIHByZXZpb3VzIHBhcmFncmFwaCkuIEZvciB0aGUgcHVycG9zZSBvZiB0aGlzIHByb2JsZW0sIGEgZGF0ZSBpcyBjb25zaWRlcmVkIHZhbGlkIGlmIHRoZSB5ZWFyIGlzIGJldHdlZW4gMSBhbmQgMjE0NzQ4MzY0NywgdGhlIG1vbnRoIGlzIGJldHdlZW4gMSBhbmQgMTIsIHRoZSBkYXkgaXMgYXQgbGVhc3QgMSBhbmQ6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+Zm9yIG1vbnRocyAxLDMsNSw3LDgsMTAsMTIgJm5kYXNoOyB0aGUgZGF5IGlzIG5vdCBncmVhdGVyIHRoYW4gMzE8XC9saT5cclxuXHQ8bGk+Zm9yIG1vbnRocyA0LDYsOSwxMSAmbmRhc2g7IHRoZSBkYXkgaXMgbm90IGdyZWF0ZXIgdGhhbiAzMDxcL2xpPlxyXG5cdDxsaT5mb3IgbW9udGggMiwgdGhlIGRheSBpcyBub3QgZ3JlYXRlciB0aGFuIDI5LCBhbmQgY2FuIGJlIDI5IG9ubHkgZHVyaW5nIGxlYXAgeWVhcnMuIEEgeWVhciBpcyBjb25zaWRlcmVkICZsZHF1bztsZWFwIHllYXImcmRxdW87IGlmIGl0IGlzIGRpdmlzaWJsZSBieSA0MDAsIG9yIGlzIGRpdmlzaWJsZSBieSA0IGJ1dCBub3QgYnkgMTAwPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBpbnB1dCBmaWxlIGNvbnRhaW5zIG9uZSBkYXRlIHBlciBsaW5lOiB0aGVlIG51bWJlcnMgc2VwYXJhdGVkIGJ5IHRoZSBjaGFyYWN0ZXIgJmxzcXVvO1wvJnJzcXVvOywgJm5ic3A7cmVwcmVzZW50aW5nIChpbiBvcmRlcikgdGhlIGRheSwgbW9udGggYW5kIHllYXIuIEZvciBleGFtcGxlLCBKdWx5IDR0aCAyMDExIHdvdWxkIGJlIHdyaXR0ZW4mbmJzcDthcyAmbGRxdW87MDRcLzA3XC8yMDExJnJkcXVvOyAob3IgNFwvMDdcLzIwMTEsIG9yIDRcLzdcLzIwMTEpLiBUaGUgbGFzdCBsaW5lIGluIHRoZSBpbnB1dCBmaWxlIGlzIGVtcHR5LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBvdXRwdXQgZmlsZSBzaGFsbCBjb250YWluIHRoZSBuZXh0IHZhbGlkIHBhbGluZHJvbWljIGRhdGUgZm9yIGVhY2ggZGF0ZSBpbiB0aGUgaW5wdXQgZmlsZSwgb25lIGRhdGUgcGVyIGxpbmUuIFRoZSBkYXRlIGZvcm1hdCBpbiB0aGUgb3V0cHV0IGZpbGUgaXMgRERcL01NXC9ZZWFyICZuZGFzaDsgaS5lLiB0aGUgc2VwYXJhdG9yIGNoYXJhY3RlciBpcyAmIzM5O1wvJiMzOTssIHRoZSB5ZWFyJnJzcXVvO3MgZmlyc3QgZGlnaXQgbXVzdCBuZXZlciBiZSAwLCBhbmQgeW91IG11c3QgYWx3YXlzIHVzZSB0d28gZGlnaXRzIGZvciBkYXkgYW5kIG1vbnRoICh1c2UgMDEgaW5zdGVhZCBvZiAxLCAwMiBpbnN0ZWFkIG9mIDIgZXRjLikuIEl0IGlzIGd1YXJhbnRlZWQgdGhhdCBhbGwgaW5wdXQgZGF0ZXMgYXJlIHZhbGlkLCBhbmQgdGhhdCBmb3IgYWxsIGlucHV0IGRhdGVzIHRoZXJlIGlzIGEgJmxkcXVvO25leHQgdmFsaWQgcGFsaW5kcm9taWMgZGF0ZSZyZHF1bzsuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d