시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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+XHJcblx0XHVjNzg1XHViODI1XHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljNCBcdWIwYTBcdWM5ZGNcdWM3NTggXHViMmU0XHVjNzRjXHVjNWQwIFx1YzYyNFx1YjI5NCBcdWQzMzBcdWI5YjBcdWI0ZGNcdWI4NmMgXHViMGEwXHVjOWRjXHViOTdjIFx1Yzc3Y1wvXHVjNmQ0XC9cdWM1ZjBcdWIzYzQgXHVkNjE1XHVkMGRjXHViODVjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVjNWYwXHViM2M0XHVjNzU4IFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjMjJiXHVjNzkwXHViMjk0IDBcdWM3NzQgXHViNDE4XHViYTc0IFx1YzU0OFx1YjQxOFx1YWNlMCwgXHVjNmQ0XHVhY2ZjIFx1Yzc3Y1x1Yzc0MCBcdWI0NTBcdWM3OTBcdWI5YWNcdWI4NWMgXHVjZDljXHViODI1XHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gKDFcdWIzMDBcdWMyZTBcdWM1ZDAgMDEsIDJcdWIzMDBcdWMyZTBcdWM1ZDAgMDIpIFx1ZDU2ZFx1YzBjMSBcdWIyZTRcdWM3NGMgXHVkMzMwXHViOWIwXHViNGRjXHViODZjIFx1YjBhMFx1YzlkY1x1YWMwMCBcdWM4NzRcdWM3YWNcdWQ1NThcdWIyOTQgXHVhY2JkXHVjNmIwXHViOWNjIFx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMzcxOSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlBhbGluZHJvbWljIERhdGVzIiwiZGVzY3JpcHRpb24iOiI8cD5BIGRhdGUgaXMgc2FpZCB0byBiZSBwYWxpbmRyb21pYyBpZiwgd2hlbiB3cml0dGVuIGluIHRoZSBmb3JtICZsZHF1bztZZWFyTU1ERCZyZHF1bzssIHRoZSByZXN1bHQgaXMgYSAmbmJzcDtwYWxpbmRyb21lIChhIG51bWJlciB0aGF0IGhhcyB0aGUgc2FtZSB2YWx1ZSByZWdhcmRsZXNzIGlmIHdlIHJlYWQgaXQgbGVmdC10by1yaWdodCBvciByaWdodC10by1sZWZ0KS4gRm9yIGV4YW1wbGUsIHRoZSBkYXRlICZsZHF1bztKYW51YXJ5IDFzdCwgMSZyZHF1bzsgaXMgcGFsaW5kcm9taWMgc2luY2UgaXQgd291bGQgYmUgd3JpdHRlbiBhcyAmbGRxdW87MTAxMDEmcmRxdW87OyZuYnNwOyZsZHF1bztEZWNlbWJlciAxc3QsIDEwMjEmcmRxdW87IGlzIHBhbGluZHJvbWljIHRvbywgc2luY2UgaXQgd291bGQgYmUgd3JpdHRlbiBhcyAmbGRxdW87MTAyMTEyMDEmcmRxdW87LjxcL3A+XHJcblxyXG48cD5HaXZlbiBhIGRhdGUsIHlvdSBhcmUgcmVxdWlyZWQgdG8gZmluZCB0aGUgbmV4dCB2YWxpZCBkYXRlIChpbiBjaHJvbm9sb2dpY2FsIG9yZGVyKSB0aGF0IGlzICZuYnNwO3BhbGluZHJvbWljIChhY2NvcmRpbmcgdG8gdGhlIGRlZmluaXRpb24gb2YgJmxkcXVvO3BhbGluZHJvbWljIGRhdGUmcmRxdW87IHRoYXQgd2FzIGdpdmVuIGluIHRoZSBwcmV2aW91cyBwYXJhZ3JhcGgpLiBGb3IgdGhlIHB1cnBvc2Ugb2YgdGhpcyBwcm9ibGVtLCBhIGRhdGUgaXMgY29uc2lkZXJlZCB2YWxpZCBpZiB0aGUgeWVhciBpcyBiZXR3ZWVuIDEgYW5kIDIxNDc0ODM2NDcsIHRoZSBtb250aCBpcyBiZXR3ZWVuIDEgYW5kIDEyLCB0aGUgZGF5IGlzIGF0IGxlYXN0IDEgYW5kOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPmZvciBtb250aHMgMSwzLDUsNyw4LDEwLDEyICZuZGFzaDsgdGhlIGRheSBpcyBub3QgZ3JlYXRlciB0aGFuIDMxPFwvbGk+XHJcblx0PGxpPmZvciBtb250aHMgNCw2LDksMTEgJm5kYXNoOyB0aGUgZGF5IGlzIG5vdCBncmVhdGVyIHRoYW4gMzA8XC9saT5cclxuXHQ8bGk+Zm9yIG1vbnRoIDIsIHRoZSBkYXkgaXMgbm90IGdyZWF0ZXIgdGhhbiAyOSwgYW5kIGNhbiBiZSAyOSBvbmx5IGR1cmluZyBsZWFwIHllYXJzLiBBIHllYXIgaXMgY29uc2lkZXJlZCAmbGRxdW87bGVhcCB5ZWFyJnJkcXVvOyBpZiBpdCBpcyBkaXZpc2libGUgYnkgNDAwLCBvciBpcyBkaXZpc2libGUgYnkgNCBidXQgbm90IGJ5IDEwMDxcL2xpPlxyXG48XC91bD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgaW5wdXQgZmlsZSBjb250YWlucyBvbmUgZGF0ZSBwZXIgbGluZTogdGhlZSBudW1iZXJzIHNlcGFyYXRlZCBieSB0aGUgY2hhcmFjdGVyICZsc3F1bztcLyZyc3F1bzssICZuYnNwO3JlcHJlc2VudGluZyAoaW4gb3JkZXIpIHRoZSBkYXksIG1vbnRoIGFuZCB5ZWFyLiBGb3IgZXhhbXBsZSwgSnVseSA0dGggMjAxMSB3b3VsZCBiZSB3cml0dGVuJm5ic3A7YXMgJmxkcXVvOzA0XC8wN1wvMjAxMSZyZHF1bzsgKG9yIDRcLzA3XC8yMDExLCBvciA0XC83XC8yMDExKS4gVGhlIGxhc3QgbGluZSBpbiB0aGUgaW5wdXQgZmlsZSBpcyBlbXB0eS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgb3V0cHV0IGZpbGUgc2hhbGwgY29udGFpbiB0aGUgbmV4dCB2YWxpZCBwYWxpbmRyb21pYyBkYXRlIGZvciBlYWNoIGRhdGUgaW4gdGhlIGlucHV0IGZpbGUsIG9uZSBkYXRlIHBlciBsaW5lLiBUaGUgZGF0ZSBmb3JtYXQgaW4gdGhlIG91dHB1dCBmaWxlIGlzIEREXC9NTVwvWWVhciAmbmRhc2g7IGkuZS4gdGhlIHNlcGFyYXRvciBjaGFyYWN0ZXIgaXMgJiMzOTtcLyYjMzk7LCB0aGUgeWVhciZyc3F1bztzIGZpcnN0IGRpZ2l0IG11c3QgbmV2ZXIgYmUgMCwgYW5kIHlvdSBtdXN0IGFsd2F5cyB1c2UgdHdvIGRpZ2l0cyBmb3IgZGF5IGFuZCBtb250aCAodXNlIDAxIGluc3RlYWQgb2YgMSwgMDIgaW5zdGVhZCBvZiAyIGV0Yy4pLiBJdCBpcyBndWFyYW50ZWVkIHRoYXQgYWxsIGlucHV0IGRhdGVzIGFyZSB2YWxpZCwgYW5kIHRoYXQgZm9yIGFsbCBpbnB1dCBkYXRlcyB0aGVyZSBpcyBhICZsZHF1bztuZXh0IHZhbGlkIHBhbGluZHJvbWljIGRhdGUmcmRxdW87LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==