Palindrome Date

Time limit5sMemory limit128 MB

Summary

Given a date, find the next date whose YearMMDD string is a palindrome, handling huge years and leap years correctly.

Level: Medium6 of 10
Topics: String, Math, Simulation
Solved: No attempts yet

Problem

A date is a palindrome if, when written as the string "YearMMDD", it reads the same forwards and backwards. Here the year is written as-is (with no leading zeros), while the month (MM) and the day (DD) are each written with two digits. For example, "year 1, month 1, day 1" becomes "10101", which is a palindrome, and "year 1021, month 12, day 1" becomes "10211201", which is also a palindrome.

Given a date, write a program that finds the next palindrome date that comes after it.

In this problem the year is between $1$ and $2147483647$ , inclusive. Leap years must be taken into account. A leap year follows the Gregorian rule: a year is a leap year if it is divisible by $4$ and not by $100$ , or if it is divisible by $400$ . February has $29$ days in a leap year.

Input

The first line contains the number of test cases $T$ . Each test case consists of one line containing a date in day/month/year format. The month and the day may or may not have leading zeros; for example, 4 July 2011 may be given as "04/07/2011", "4/07/2011", "4/7/2011", or "04/7/2011".

Output

For each test case, print the next palindrome date after the given date, in day/month/year format. The first digit of the year must not be $0$ , and the month and day must always be printed with two digits (for example, 01 instead of 1, and 02 instead of 2). The input is guaranteed to only contain cases for which a next palindrome date exists.

Examples5

Example 1

Input

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

Expected output

01/02/1
11/12/1
31/08/138048984

Example 2
Input
```
1
4/7/2011
```
Expected output
```
02/11/2011
```
Example 3
Input
```
1
04/07/2011
```
Expected output
```
02/11/2011
```
Example 4
Input
```
1
31/12/1
```
Expected output
```
02/01/2
```
Example 5
Input
```
1
28/02/9220
```
Expected output
```
29/02/9220
```