DIV15 - Divisibility by 15

no tags 

There is a string containing only decimal digit characters. The length of the string is between 1 and 1000. Using characters of the string, you have to construct the maximum number which divides by fifteen without remainder. Each character of the string may not be used more than once.

Input

First line of input contains an integer t (1 ≤ t ≤ 90), equal to the number of test cases. Then descriptions of t test cases follow.

Each testcase is described in a single line representing the source string.

Output

For each test case output one line with the decimal representation of the maximum number. Leading zeroes should be omitted. If no number can be constructed, output a single word “impossible”.

Example

Input:
1
02041

Output:
4200

hide comments
Brian Bi: 2009-04-19 02:34:54

The input file contains DOS-style newlines. This recently caused a friend considerable difficulty as the C gets() function on *nix will actually read in the carriage return character, causing unexpected behaviour. Please correct this.


Added by:Ivan Metelsky
Date:2005-08-25
Time limit:1.919s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS PERL6 VB.NET
Resource:NEERC Western Subregion QF 2004