You are given three integers $a$, $b$, and $n$. Your task is to determine the number of positive integers $x\in[1,10^9]$ such that $ax^x$ is an n-digit number of base $b$.

Input format

The input contains many test cases. Each test case is represented in a new line. Every line contains three integers, a, n, and b ($1\leq a,n\leq 10^9,2\leq b\leq 10$)

Note: There are at most 1000 test cases.

Output format

For each test case, print the answer.