Arush was not always poor at Mathematics but his recent performances had not been that good and he had lost his confidence. Now his elder brother was determined to bring back his confidence back in Mathematics.
So he made a tricky question and made sure that Arush would be able to do solve it. The factorial of a non-negative integer n, denoted by n! , is the product of all positive integers less than or equal to n.
n! = n * (n-1) * (n-2) * ...... * 1

Arush’s elder brother so defined a function F(x) for positive integer x as the product of factorials of its constituting digits.
For example, F(125) = 1! * 2! * 5!.
You are given a number N that contains d digits and contains at least one digit larger than 1.
The problem is to find maximum positive number M which should contain neither the digit 0 nor the digit 1 and also F(M) = F(N).
The number N may possibly start with leading zeroes.
Help Arush to bring his confidence back.

Input

The first line of input contains T, the number of testcases.
The first line contains an integer d, number of digits in N.
Next line contains d digits of N.

Output

Output the maximum possible integer M that satisfies the above conditions.

Constraints
Should contain all the constraints on the input data that you may have. Format it like:

1 ≤ T ≤ 50
1 ≤ d ≤ 15

Example
Input:
2
1
6
3
006

Output:
53
53

Explanation
Example case 1. d = 1, N = 6. Now F(6) = 6! = 720 and F(53) = 5! * 3! = 120 * 6 = 720.

见题面

见题面