DIV15 - Divisibility by 15

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

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

hide comments
2021-10-28 04:18:46
What a nightmare!

try this:
Input:
1
98495
Output:
9945
2017-12-19 02:47:44
What a nightmare.. Spent 2.5 hours debugging to finally AC with the ugliest, dumbest code I've ever written.. Then again with 5245 out of 8381 submissions for this problem being WA's, elegance has to take the back seat.
2016-12-20 09:43:30
Some string manipulation and rest number theory!!! XD XD
Make sure you remove all the trailing zeroes XD
costed me 1 WA :(
2016-05-21 08:02:26 rainy jain
@Ivan I'm getting SIGXFSZ . Please check id:16956224
2014-09-09 22:37:46 Devashish Mathur
Please someone tell me which test case am i missing?
12339290 - Submission ID
2013-12-07 08:16:58 DEBAJIT DEY
what should be the output for 20
0 or impossible
2013-08-14 13:02:33 nadavishe
All time runtime error. But on my mashine tested many cases - and all is OK. Please help - my submission ID-9836707. Thanks
2013-07-29 06:54:27 wgjak47
ATTENTION!!DON'T USE gets() or fgets(),or you will get wrong answer.the input file must come from windows,but the judge computer is linux,they don't have the same line break.....
2013-06-08 21:33:17 UTSAV DEEP
always getting wrong ans
any special test cases... plz


Last edit: 2013-06-09 08:57:59
2013-02-25 13:15:20 [Lakshman]
please any hint for this problem...
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.