给定两个整数 $n$ 和 $k$。

请你计算，末尾至少有连续 $k$ 个 $0$，并且可以被 $n$ 整除的最小正整数。

例如，当 $n=375,k=4$ 时，满足条件的最小正整数为 $30000$。

输入格式

第一行包含整数 $T$，表示共有 $T$ 组测试数据。

每组数据占一行，包含两个整数 $n,k$。

输出格式

每组数据输出一行结果，表示满足条件的最小正整数。

数据范围

所有数据满足 $1 \le T \le 10$，$1 \le n \le 10^9$，$0 \le k \le 8$。

输入样例：

6
375 4
10000 1
38101 0
123456789 8
1 0
2 0

输出样例：

30000
10000
38101
12345678900000000
1
2