Hệ cơ số

Trong một buổi tập bơi, FullHouse Dev được huấn luyện viên đưa ra một bài toán thú vị về hệ cơ số. Sau khi hoàn thành vòng bơi thứ 100, các thành viên đã cùng nhau ngồi bên hồ bơi và bắt đầu giải quyết bài toán này.

Bài toán

FullHouse Dev được cho ba số nguyên \(a\), \(n\) và \(b\). Nhiệm vụ của họ là xác định có bao nhiêu số nguyên dương \(x\) thỏa mãn điều kiện: khi biểu diễn \(a^x\) trong hệ cơ số \(b\) sẽ có đúng \(n\) chữ số.

INPUT FORMAT:

• Input gồm nhiều test case, mỗi test case nằm trên một dòng mới
• Mỗi dòng chứa ba số nguyên \(a\), \(n\) và \(b\) (\(2 \leq b \leq 10^9\))
• Lưu ý: Có tối đa 1000 test case

OUTPUT FORMAT:

• Với mỗi test case, in ra số lượng giá trị \(x\) thỏa mãn điều kiện

Ví dụ

INPUT

1 2 10
1 1 10

OUTPUT

1
2

Giải thích

Input gồm 2 test case:

• Ở test case thứ nhất: \(x = 3\) thỏa mãn điều kiện
• Ở test case thứ hai: \(x = 1\) và \(x = 2\) thỏa mãn điều kiện