T582965 L3-1 最小大小数

观察以下神奇的等式： $$ \begin {aligned} 3^4 \cdot 425 & = 34 \, 425 \\ 31^2 \cdot 325 & = 312 \, 325 \\ 3^4 \cdot 7^2 \cdot 875 & = 3 \, 472 \, 875 \end {aligned} $$ 这些等式均出自哔哩哔哩（又名 Bilibili、B 站）视频 up 主“聚四苯乙烯”上传的视频《数学老师：欠扁是吧05》。（第一个等式与原视频不同。视频链接见题目末尾。**请赛后再观看视频！**）有些人“不小心看错”有些题目，却算出了正确答案。许多网友不淡定了，纷纷发送弹幕表示惊讶。  不难观察出，使用错误解法的人，有意无意地“看错”了数字的大小和位置，把它们当成在一条水平线上，还“看漏”了乘号，从而“直接”得出答案；题目也是精心构造的，目的就是让这种算法能算出正确答案。不过需要指出的是，这种计算方法并不正确。对绝大多数题目应用这种算法，都会算出错误答案，例如 $2^3 \cdot 5 \ne 235$。 我们当然不用像视频一样凑等式，这种等式可遇而不可求。我们要做的是仿照视频的出题方法，根据已有的数凑出**最小**的数。 给定一个十进制数字串 $A = A_{N - 1} A_{N - 2} \cdots A_1 A_0$，其中**每一位都不为** $\bm 0$。我们可以对其进行一次“大小数变换”，得到一个表达式。 “大小数变换”指：先选择十进制数字串中的任意多个数位（可不选，不能选最高位），把这些数位上的数字缩小并上移到指数位置；再在所有指数数字之后、非指数数字之前补上一个乘号（$\cdot$）。这样就形成了一个只包含乘法和乘方运算的表达式。 例如，对于 $3 \, 472 \, 875$，选择第 $1$、$3$ 位变换，可变成 $347^2 \cdot 8^7 \cdot 5$；选择第 $0$、$2$、$3$、$5$ 位变换，可变成 $3^4 \cdot 7^{28} \cdot 7^5$。但是，不可选择第 $6$ 位（最高位）变换，变成 $^3 \cdot 472 \, 875$。 又如，变换 $34 \, 425$ 可能得到的所有表达式有：$34 \, 425$、$3 \, 442^5$、$344^2 \cdot 5$、$344^{25}$、$34^4 \cdot 25$、$34^4 \cdot 2^5$、$34^{42} \cdot 5$、$34^{425}$、$3^4 \cdot 425$、$3^4 \cdot 42^5$、$3^4 \cdot 4^2 \cdot 5$、$3^4 \cdot 4^{25}$、$3^{44} \cdot 25$、$3^{44} \cdot 2^5$、$3^{442} \cdot 5$、$3^{4 \, 425}$，共 $16$ 种。 当然，我们不允许随意添加乘号，例如视频截图所示的 $3^5 \cdot 7 \cdot 21$ 中，$7$ 不是指数数字，故 $7$ 和 $2$ 之间不能添加乘号。 对 $A$ 进行“大小数变换”得到的表达式，其计算结果称为 $A$ 的“大小数”。 请计算 $A$ 的所有“大小数”中的最小值。

输入第一行给出一个正整数 $T$（$\le 5 \cdot 10^3$）表示测试用例的个数。 每个测试用例第一行给出一个正整数 $N$（$\le 18$）；第二行给出一个十进制数字串 $A_{N - 1} A_{N - 2} \cdots A_1 A_0$（$1 \le A_i \le 9$）。

对于每个测试用例，在一行中输出一个整数，表示 $A$ 的所有“大小数”中的最小值。

在第一个样例中，可变换成 $3^4 \cdot 4^2 \cdot 5 = 6480$。 在第二个样例中，可变换成 $3572^1 = 3572$。 在第三个样例中，可变换成 $3^1 \cdot 2^3 \cdot 25 = 600$。 在第四个样例中，无需变换。 在第五个样例中，可变换成 $1^{23} = 1$。 在第六个样例中，可变换成 $3^2 \cdot 1 = 9$。 在第七个样例中，可变换成 $2^2 \cdot 2^2 \cdot 2^2 \cdot 2^2 \cdot 2^2 = 1024$。 --- --- --- --- --- --- --- --- --- --- **【备注】** 视频链接：[《数学老师：欠扁是吧05》（精准空降 00:05）](https://www.bilibili.com/video/BV1XL4119737/?t=5)（**请赛后再观看视频！**）