Nikifor knows that a certain positive integer has in its decimal form each of the digits 1,2,3,4. You are asked to determine if Nikifor can rearrange the digits of the number in such a way that the new number divides by 7.

The first line contains the number N (not exceeding 10000) of positive integers that are to be checked. The next N lines contain these integers. Each number has no more than 20 digits.

For each of the N numbers output a number divisible by 7 that can be obtained from the corresponding number 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 find only one of them.