This problem is a programming version of Problem 170 from projecteuler.net
Take the number and multiply it by each of and :
By concatenating these products we get the to pandigital . We will call the "concatenated product of and (,)". Notice too, that the concatenation of the input numbers, , is also to pandigital.
The same can be done for to pandigital numbers.
What is the largest to pandigital -digit concatenated product of a positive integer with two or more other positive integers (all integers without leading zeroes), such that the concatenation of the input numbers is also a to pandigital -digit number and the concatenated product is not greater than ?
Input Format
The first line of input contains a single integer which is the number of test cases. Each of the lines contain a single integer .
Constraints
- is to pandigital number without leading zeroes.
Output Format
For each from input, output the multiplications which produce the maximum pandigital product. Answer always exists but if there are several sets of these multiplications, choose the one with the best representation. Definition of the best representation is as follows:
- Let's assume that the maximum pandigital can be represented as a product of and . Also it can be represented as a product of and . Notice that and are positive and have no leading zeroes .
- If , then the best representation is the one with the least . Otherwise, look .
- If , then the best representation is the one with the least . Otherwise, look .
- If for some the following is true: and then the first representation is the best if and only if .
Output should match the following pattern:
a*(b_1,b_2,b_3...)=P
Refer sample for further clarification.
Sample Input 0
1
2840571693
Sample Output 0
3*(94658,2170)=2839746510
Explanation 0
As one can notice, and