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\)