ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

1095. Nikifor 3

Time limit: 1.0 second
Memory limit: 64 MB
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.

Input

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.

Output

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.

Sample

inputoutput
2
1234
531234
4123
354123
Problem Author: Dmitry Filimonenkov
Problem Source: USU Open Collegiate Programming Contest March'2001 Senior Session