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
saket diwakar: 2013-01-26 18:38:12

good one.....:)

Mostafa 36a2: 2012-10-27 20:58:29

For who got wa
just try those 2 test cases
8885
88850
i found my mistake here
solve it then ac ,thanks for GOD

Prakash: 2012-10-14 14:52:49

i am getting WA since my code passes all testcases i entered and the given test cases in comments too..help plz..

ViNiTH: 2012-08-24 16:41:19

:\ changing getchar to scanf fixed the WA

Romal Thoppilan: 2011-09-01 18:35:08

How should we take the input ?
i am not quite familiar with dos style newlines .

Rajesh Kumar: 2011-07-30 19:50:01

please give the correct output for:
0
00
0402
00004

Peutri: 2010-08-31 20:30:36

I've got to second All-American Reject on this: those \r are a real pain. If you don't intend to format the input using the platform's native line format (which most languages tend to read fine by default), at least make it explicit in the official input description.

cjtoribio: 2010-07-26 00:37:16

Input:
1
20000000000
Output:
0

Note: be carefull you should output just ONE zero

AlB80: 2009-06-30 07:45:11

"Leading zeroes should be omitted." means
Input:
3
0
00
000
Output:
0
0
0

Marcin Tomasik: 2009-06-29 14:27:35

I have AC
It should be
Input:
1
0
Output
0


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