Mùa thi ở đại học Zagreb vừa kết thúc và sinh viên ngày càng ngủ nhiều hơn. Trong những thời gian tỉnh táo hiếm hoi thì họ thường lướt Instagram. Fabijan là một sinh viên như thế.

Gần đây, cậu đọc được một caption rằng ngày 02.02.2020 là ngày "palindrome" đầu tiên trong ~909~ năm gần nhất. Cậu nhận ra caption này sai và biết trước một ngày bất kì, sớm nhất khi nào sẽ lại có một ngày palindrome sau ngày đó? Fabijan sẽ trả lời câu hỏi trên với ~N~ ngày bất kì biết trước.

Một ngày (theo format DD.MM.YYYY.) được gọi là ngày "palindrome" nếu bỏ các dấu chấm thì thu được một xâu kí tự mà khi viết lại từ trái sang phải hay phải sang trái đều như nhau. Ví dụ 02.02.2020. là một ngày palindrome vì khi bỏ hết dấu chấm, ta thu được xâu 02022020. Xâu 02022020 dù viết lại từ trái sang phải hay phải sang trái thì vẫn thu được chính nó. Như vậy, 02.02.2020. và 12.10.0121 là những ngày palindrome và 03.02.2020 hay 12.07.1993 không được gọi là ngày palindrome.

P/S: Lưu ý rằng tháng ~2~ của năm nhuận có ~29~ ngày. Trong phạm vi đề bài, giả sử rằng năm nhuận là các năm chia hết cho ~4~. Ngoài ra, các tháng trong năm có ~31~, ~28~, ~31~, ~30~, ~31~, ~30~, ~31~, ~31~, ~30~, ~31~, ~30~, ~31~ ngày theo thứ tự như bình thường.

Input

Dòng đầu tiên chứa số nguyên dương ~N~ (~N \leq 10000~). Mỗi dòng trong ~N~ dòng tiếp theo chứa một ngày theo format DD.MM.YYYY..

Output

Với mỗi ngày trong ~N~ ngày cho trước, in ra ngày palindrome gần nhất trả lời cho câu hỏi của Fabijan dưới dạng DD.MM.YYYY. Dữ liệu bảo đảm đáp án tồn tại.

Ví dụ

Sample input 1

1
02.02.2020.

Sample output 1

12.02.2021.

Sample input 2

2
01.01.1000.
31.12.2026.

Sample output 2

10.01.1001.
03.02.2030.

Sample input 3

3
01.01.0100.
05.07.0321.
05.05.0505.

Sample output 3

10.10.0101.
10.01.1001.
10.01.1001.

Ghi chú

Ở ví dụ đầu tiên, tuy 02.02.2020. là một ngày palindrome nhưng Fabijan chỉ quan tâm đến ngày palindrome gần nhất sau ngày đó. Vì thế kết quả là 12.02.2021.