萨格勒布大学的考试季结束了，学生们正在做他们最喜欢的事情——睡觉。在极少数清醒的时刻，他们通常会刷 Instagram 动态。Fabijan 就是这些学生之一。

最近，他读到了这样一条配图文字——日期 02.02.2020. 是过去 909 年里的第一个回文日期。

他意识到这个配图文字是错误的，这让他对回文日期产生了好奇。于是他问自己，对于给定的 $N$ 个日期中的每一个，在它之后严格出现的第一个回文日期是什么？如果忽略点号（.），一个日期从左往右读和从右往左读是完全相同的，则该日期被认为是回文的。例如，日期 02.02.2020. 和 12.10.0121. 是回文的，而 03.02.2020. 和 12.07.1993. 则不是。

注意：在本题中，考虑 2 月有 29 天的闰年非常重要。为了本题的目的，我们认为如果年份能被 4 整除，则该年为闰年。否则，各个月份的天数依次为 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30 和 31 天。

输入格式

第一行包含一个整数 $N$ ($1 \le N \le 10\,000$)，含义如题面所述。

接下来的 $N$ 行，每行包含一个格式为 DD.MM.YYYY. 的有效日期。

输出格式

对于输入中的每个日期，输出在它之后严格出现的第一个回文日期。

该日期应以 DD.MM.YYYY. 的格式打印，我们保证在此格式下一定存在解。

子任务

• 在价值 10 分的测试用例中，输出中的每个日期与输入中对应的日期具有相同的月份和年份。此外，$N = 10$。
• 在额外价值 10 分的测试用例中，输出中的每个日期与输入中对应的日期具有相同的年份。此外，$N = 10$。
• 在额外价值 20 分的测试用例中，满足 $N = 10$。

样例

输入样例 1

1
02.02.2020.

输出样例 1

12.02.2021.

输入样例 2

2
01.01.1000.
31.12.2026.

输出样例 2

10.01.1001.
03.02.2030.

输入样例 3

3
01.01.0100.
05.07.0321.
05.05.0505.

输出样例 3

10.10.0101.
10.01.1001.
10.01.1001.

说明

第一个样例的解释：尽管给定的日期本身就是回文的，但 Fabijan 感兴趣的是在它之后严格出现的第一个日期。该日期为 12.02.2021.。