Migrated from Lutece 221 Counting Problem

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Snoworld just entered middle school. His math teacher enjoyed asking him strange questions. One of the questions is that how many numbers are there from $1$ to $K$ that doesn’t contain any $M$. For example, if $K$ equals $5$ and $M$ equals $3$, the answer would be $4$ and if $K$ equals $11$ and $M$ equals $1$, the answer would be $8$. Snoworld solved the question rather easily. So teacher complicated the question by asking it in an $N$-base system and required the answer to presented in an $n$-base system, so the $K$ and $M$ is $N$-base number. For example, if $K$ equals $22$ and $M$ equals $1$ and $N$ equals $3$, all the numbers are $1, 2, 10, 11, 12, 20, 21, 22$ and the answer is $10$.

Input

The first line of the input is an integer $C$ representing the number of cases, while is no more than $30$.

The following $C$ lines each contain three integers $K, M$ and $N$.

$K$ has no more than $9$ digits. $0 < M < 10, 1 < N \leq 10, M < N$.

Output

For each test case print one line with the answer presented in an $N$-base system.

Samples

3
11 1 10
22 1 3
36 5 9

8
10
32

Resources

第四届北京邮电大学程序设计竞赛网络预赛