题目描述

给出一个长度为 \(n\) 的数，要在其中加 \(m-1\) 个乘号，分成 \(m\) 段，这 \(m\) 段的乘积之和最大, \(m<n<18\) ;有 \(T\) 组数据，\(T<=10000\)。

格式

输入格式

输入第 \(1\) 行一个整数 \(t\)，表示数据组数。
接下来一共 \(t\) 行，每行两个整数，第 \(1\) 个整数表示要分段的整数，第 \(2\) 整数表示 \(m\)，即要分成的段数。

输出格式

输出一共 \(t\) 行，每行一个整数，表示分成 \(m\) 段后能得到的最大乘积。

样例1

输入样例1

1
1231 3

输出样例1

62

提示

可以先预处理出原数从第 \(i\) 位到第 \(j\) 位的区间的数值 \(A[i][j]\) 是多少，这样转移就方便了，预处理也要尽量降低复杂度。\(F[i][j]\) 表示把这个数前 \(i\) 位分成 \(j\) 段得到的最大乘积。
f[i][j]=max(f[i][j],f[k][j-1]*a[k+1][i]),
\(1<k<i<=n, j<=m\)