B. 欢庆节日!

内存限制:16 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较

题目描述

今天是地底世界重见光明的纪念日!

为了庆祝这历史性的一天,在节日庆典上Toriel做了一些巨大的蛋糕,有m位居民参加了这场庆典,现在Frisk要帮她把蛋糕分给所有来参加庆典的居民。

蛋糕非常的长——每一小段蛋糕都有一个“美味值”,“美味值”是一个 之间的整数,一大块蛋糕的“美味值”是组成这块大蛋糕的每一小段蛋糕的美味值的十进制表示,最终的“总美味值”就是每一块蛋糕的美味值的乘积。(简单来说,就是在一段连续的数中加入m-1个乘号将其分隔开,使得结果最大)

Frisk希望能让每个蛋糕的“总美味值”最大,但是Frisk想了很久也没想出最优解,所以Frisk来请你帮忙。

输入格式

行 第 个正整数 ,表示有多少个蛋糕 接下来 行,奇数行 个只含 数字的字符串,偶数行 个整数,表示有多少居民参加

输出格式

行 每行 个整数,表示这个蛋糕的最大“总美味值”

样例

【样例输入】

1
5555555
2

【样例输出】

3083025

【样例输入】

1
123654789
3

【样例输出】

89031384

数据范围与提示

通告标题

通告内容

已知晓