You are given an integer $N$ and your task is to make $N$ a multiple of 3. In order to make $N$ multiple of 3, you can insert at most one digit in $N$.

Your task is to find the minimum possible $N$ which is a multiple of 3 after inserting at most one digit.

Note: You can insert the digit anywhere in $N$ and also you need not necessarily insert.

Input format

• The first line contains an integer $T$ denoting the number of test cases.
• The first line of each test case contains an integer $N$.

Output format

For each test case:

• Print the minimum $N$ which is a multiple of 3 after at most one insertion.

Constraints

• $1 \leq T \leq 20000$
• $1 \leq N \leq 10^9$