A number $n$ is said to be special if the sum of its digits is divisible by 4.

For a given integer $a$, find a number $n$ such that:

• $n$ is a special number
• $n \ge a$
• $n$ is minimum possible

Input format

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

Output format

For each test case, print a number $n$ that satisfies the above conditions in a new line.

Constraints

$1 \le T \le 10^ 5 \\ 1 \le a \le 10^3$