34766번 - 쿠의 용돈 인상 계획

문제

쿠는 건국대학교의 마스코트답게 매년 총장에게 용돈을 $N$원 받는다. 쿠는 언젠간 건국대학교를 인수하기 위해 용돈을 $x$배 올려달라고 부탁했다 $(2 \le x \le 9;\ x$는 정수$)$.

총장은 쿠의 능력을 시험하기 위해 용돈을 $x$배 올려주는 대신, 쿠에게 $N$의 자릿수 중 하나를 고르게 하고, 그 수에 $x$배를 하여 바꾼 금액으로 인상해 주겠다고 한다.

다시 말해, 쿠는 다음과 같은 일련의 방법으로 용돈을 인상 받을 수 있다.

• 양의 정수 $x$를 하나 고른다. $x$가 시행마다 같을 필요는 없다.
• $N$의 자릿수 중 하나를 고르고, 이를 $y$라 하자.
• $y := xy$로 교체한다.

예를 들어, 쿠의 용돈이 23ドル,000円$원이라고 하자. 쿠는 $x=4$를 임의로 선택하고, 23ドル,000円$의 자릿수인 3ドル$을 선택하여 3ドル$을 4ドル$배 한 뒤, 2ドル\underline{3},000円 \rightarrow 2\underline{12},000円$원으로 인상 받을 수 있다.

쿠가 이와 같은 방식을 반복해서 용돈을 $K$번 인상 받는다면, 그때의 용돈의 최댓값이 얼마가 될지 궁금해졌다. 호기심이 많은 쿠를 위해 정답을 구해보자!

입력

첫째 줄에 테스트 케이스의 수를 의미하는 정수 $T$가 주어진다. $(1\leq T\leq 1,000円)$

각 테스트 케이스는 다음 두 줄로 구성된다.

• 첫째 줄에 쿠의 현재 용돈인 양의 정수 $N$의 자릿수를 의미하는 정수 $D,ドル 인상 받을 횟수를 의미하는 정수 $K$가 공백으로 구분되어 주어진다. $(1 \le D,,円K \le 100,000円)$
• 둘째 줄에 쿠의 현재 용돈을 나타내는 $D$자리의 양의 정수 $N$이 주어진다.

모든 테스트 케이스에 대하여 $D$의 합과 $K$의 합이 각각 100ドル,000円$을 초과하지 않는다.

출력

각 테스트 케이스에 대하여 쿠가 최적의 방법으로 용돈을 $K$번 인상 받았을 때 용돈의 최댓값을 출력한다.

제한

힌트