Palindromic Dates

Time limit1sMemory limit512 MB

Summary

For each given date, find the next strictly later date that reads the same forwards and backwards ignoring the dots, accounting for leap years.

Level: Medium6 of 10
Topics: Implementation, Simulation, Brute force, Math
Solved: No attempts yet

Problem

The exam season at University of Zagreb is over and students are doing what they love the most: sleeping. In the rare moments of wakefulness, they usually scroll through their Instagram feed. Fabijan is one of those students.

Recently, he read the following caption: the date 02.02.2020. is the first palindromic date in the last 909 years.

He realized the caption was incorrect, and this made him wonder about palindromic dates, so he asked himself for each of the N dates what the first palindromic date after that date is. A date is palindromic if, when disregarding the dots, it reads the same from left to right as from right to left. For example, the dates 02.02.2020. and 12.10.0121. are palindromic, while 03.02.2020. and 12.07.1993. are not.

Note: in this task it is important to take leap years into account, since they have 29 days in February. For the purposes of this task, we consider a year to be a leap year if it is divisible by 4. Otherwise, the months have 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30 and 31 days, in that order.

Input

The first line contains an integer N (1 ≤ N ≤ 10 000) from the problem description.

The next N lines contain a valid date in the format DD.MM.YYYY.

Output

For each date from the input, output the first palindromic date that comes strictly after it. Print that date in the format DD.MM.YYYY.. The answer is guaranteed to exist in this format.

Examples3

Example 1
Input
```
1
02.02.2020.
```
Expected output
```
12.02.2021.
```

Example 2

Input

2
01.01.1000.
31.12.2026.

Expected output

10.01.1001.
03.02.2030.

Example 3

Input

3
01.01.0100.
05.07.0321.
05.05.0505.

Expected output

10.10.0101.
10.01.1001.
10.01.1001.