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$