Nikifor has a certain positive integer containing each of the digits 1, 2, 3, 4 in its decimal form. He asks you to rearrange the digits of this integer in such a way that the new integer divides by 7.

The first line contains an integer N that is a number of integers to be checked (1 ≤ N ≤ 10000). The next N lines contain these integers. Each integer is positive and has no more than 20 digits.

For each of the N integers output an integer divisible by 7 that can be obtained from the corresponding integer from the input data by a rearrangement of the digits. If such rearrangement does not exist you should output 0 in the corresponding line. In the case of several valid rearrangements you may output any one of them.