Orange的阶乘

题目描述

我们都知道，在组合数学中，阶乘这一运算起到了非常关键的作用，其定义如下:

Orange学习完阶乘之后，对阶乘非常感兴趣，同时，他定义了一个自己的阶乘符号 ?，其定义具体如下:

Orange知道这个数一定会很大，而且末尾一定会有一大堆数字 $0$ ，因此他想请你帮他计算出$n?$ 末尾去掉尾缀 $0$ 之后的后 $k$ 个数字是多少？

tips: 题面中的 $\prod_{i=1}^n f(i) = f(1) \times f(2) \times ... \times f(n)$，即表示将 $f(i)$ 连乘起来。

输入格式

输入共包含 $T + 1(1\leq T \leq 10^5)$ 行，第一行为一个整数 $T$，表示Orange的询问次数，后面的每一行包含两个整数 $n(1 \leq n \leq 5 \times 10^6)$ 和 $k(1\leq k < 9)$，均为上述字母含义。

输出格式

你需要输出 $T$ 行，每行一个整数，代表Orange每次提问的回答，如果答案不足 $k$ 位，请使用前导零补齐至 $k$ 位。

样例 #1

样例输入 #1

3
1 4
5 2
114514 4

样例输出 #1

0001
56
7248

提示

#样例解释2

当 $n = 5， k = 2$ 时，$n? = 1! \times 2! \times 3! \times 4! \times 5! = 1 \times 2 \times 6 \times 24 \times 120 = 34560$。其去掉尾缀$0$之后为$3456$，后 $2$ 位为 $56$。