当前没有测试数据。

题目描述

For little pupils, a very large number usually means an integer with many many digits. Let's define a class of big integers which consists only of the digit one $(11 \cdots 1)$. The first few integers in this class are $1, 11, 111, 1111 \cdots$. Denote $\ A(n)$ as the $\ n$-th smallest integer in this class. To make it even larger, we consider integers in the form of $A(a^b)$. Now, given a prime number p\ p p, how many pairs $\ (i, j)$ are there such that $1 \leq i \leq n,\ 1 \leq j \leq m,\ A(i^j) \equiv 0(mod \ p)$.

输入格式

The input contains multiple cases. The first line of the input contains a single integer $T \ (1 \le T \le 100)$, the number of cases. For each case, the input consists of a single line, which contains 3 positive integers $p, n, m \ (p, n, m \leq 10^9)$.

输出格式

Print the answer, a single integer, in one separate line for each case.

样例

样例输入 1

2
11 8 1
7 6 2

样例输出 1

4
2