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.