题目背景

雨雾朦胧。

空翠湿人衣。

ys想知道$\pi$小数点后$k(k≤10^4)$位的值。($\color{#125BCD} \small \texttt{不就是...}$)

不过xjy太蒟蒻了，最终改成了这题。(但是数据变大了!!!)

注: 快速幂，指快速计算$a^b\%p$的值。

题目描述

给出正整数$a$，$b$，计算分数$\Large \frac{a}{b}$化成十进制小数后，小数点后第$k$位的数码。

格式

输入格式

输入包含多组数据

第$1$行，$1$个正整数$T$表示有$T$组测试数据

接下来$T$行，每行$3$个整数$a$,$b$,$k$

输出格式

输出$T$行，对于每组数据，输出$\Large \frac{a}{b}$小数点后第$k$位

4
1 7 2
1 65536 5
7 91 200
1 998244353 998244352

4
1
7
3

数据范围

$1≤T≤1000,1≤a,b,k≤2\times 10^{10}$