题目描述

给出两个整数 $n, m$ ，要求在 $n$ 中加入 $m-1$ 个乘号，将 $n$ 分成 $m$ 段，求出这 $m$ 段的最大乘积。

输入格式

第一行是一个整数 $T$，表示有 $T$ 组测试数据。
接下来 $T$ 行，每行有两个正整数 $n,m$（$1 \le n \lt 10^{19}, 0 \lt m \le n$ 的位数）。

输出格式

对于每组测试数据，输出一行一个整数，用于表示这组数据对应的结果。

2
111 2
1111 2

11
121