提示: 欢迎访问OurACM平台。
Problem 1895 整除45问题

Accept: 144    Submit: 724
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

给定只包含数字[0..9]的数字串,求使用数字串中的数字,构建一个能够整除45 最大的整数。注意,数字串中的每个数字只能使用一次。
求由给定数字串构建的能够整除45的最大整数。

Input

第一行一个数字T(1<=T<=100),表示测试数据组数。
接下来T行,每行代表一组测试数据,每组测试数据包含一个[0..9]的数字串,数字串的长度为 1..1000。

Output

对于每组测试数据,输出一行构建出的最大整数,如果无法构建出能够整除45的整数(注意:前勿输出前导0),请输出一行“impossible”。

Sample Input

6 02071 8255460 22343 33 5555555555 01111111111

Sample Output

7200 65520 impossible impossible 555555555 1111111110

Source

福州大学第七届程序设计竞赛

Submit  Back  Status  Discuss