Project Euler #118: Pandigital prime sets

_{This problem is a programming version of Problem 118 from projecteuler.net}

Using all of the digits 1 through 9 and concatenating them freely to form decimal integers, different sets can be formed. Interestingly with the set {2,5,47,89,631}, all of the elements belonging to it are prime.

You are given a nonempty set of distinct digits from 1 to 9 (i.e. a nonempty subset of {1,2,...,9}). Your task is to generate all distinct sets using each of the digits in the set exactly once and contain only prime elements, and output their sums in sorted order.

Input Format

The first line contains an integer denoting the number of test cases.

Each test case consists of a single line containing a string of distinct digits in increasing order, denoting the set.

Constraints

But in test files worth half the total score, .
Each test case is distinct.

Output Format

For each test case, output the required numbers in sorted order, one in each line.

Output a blank line after each test case.

Sample Input

2
123
1235

Sample Output

Explanation

For the first test case, the set of digits is {1,2,3}, and the following sets contain only primes:

For the second test case, the set of digits is {1,2,3,5}, and the following sets contain only primes:

Don't forget to output a blank line after each test case.