숫자 카드 놀이
시간 제한1초메모리 제한512 MB
숫자 카드 묶음을 6과 9를 회전으로 바꿀 수 있다는 조건 아래 두 수로 나누어 모든 카드를 사용할 때 곱이 최대가 되도록 만든다.
문제
Albert는 n장의 숫자 카드를 가지고 있다. 각 카드에는 0부터 9까지의 숫자 하나가 적혀 있고, 6이나 9가 적힌 카드는 회전하면 구분할 수 없다. 즉 6이 적힌 카드는 회전하면 9로 보이고, 9가 적힌 카드는 회전하면 6으로 보인다.
Albert는 두 수의 곱셈을 배운 뒤, n장의 카드를 모두 사용해 두 개의 수를 만들고 그 곱이 최대가 되게 하려고 한다. n장의 카드를 모두 사용해야 하며, 각 수는 최소 1장, 최대 n-1장의 카드로 구성된다. 6이나 9가 적힌 카드는 Albert가 임의로 회전해 사용할 수 있다.
예를 들어 n = 8이고 카드가 [2, 0, 2, 0, 2, 0, 2, 1]이라 하자. 8장의 카드로 "2200"과 "2210"을 만들면 곱은 4862000이 된다. "2020"과 "2021"을 만들어 곱이 4082420이 되게 할 수도 있다. 이 예제에서 Albert가 만들 수 있는 최대 곱은 4862000이다.
Albert가 가진 n장의 숫자 카드가 주어졌을 때, 달성 가능한 최대 곱을 구하시오.
입력
첫 줄에 테스트 케이스의 수 T가 주어진다.
다음 각 줄에 Albert가 가진 숫자 카드를 표현하는 문자열이 공백 없이 주어지며, 문자열의 각 문자는 '0'부터 '9' 중 하나이다.
출력
각 테스트 케이스에 대해 Albert가 만들 수 있는 최대 곱을 출력한다.
제한
- 1 ≤ T ≤ 10
- 2 ≤ n ≤ 18
- 모든 입력에 대해 정답은 항상 이하이다.