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 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.

Input

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.

Output

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.

Sample

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