A special birth date is $$D$$. Your task is to find the last palindrome date that comes before a date $$D$$. 

You are given a date $$D$$ in the string format. The date format is as follows:

• A valid date $$D$$ is of length 8 and in the $$ddmmyyyy$$ format.
• A valid date ranges between 01 to 30.
• A valid month ranges between 01 to 12.
• A valid year ranges between 0001 to 9999.

Input format

• The first line contains an integer $$T$$ denoting the number of test cases.
• The first line of each test case contains a string $$D$$ that denotes the special birth date.

Output format

For each test case, print the valid palindrome date in a new line. If there is no possible palindrome date that comes before D, then print -1.

Constraints

\(1 \le T \le 10000\)