Integer Sequence

Points: 30 (partial)

Time limit: 1.0s

Memory limit: 64M

Author:

Problem type

We define the sequence \(\left(U_n\right)_{n \in \mathbb{N}}\) by: \( \begin{cases} U_0 = a \\ U_{n+1} = U_{n}\cdot \dfrac{p}{q} \end{cases}. \)

Given the integers \(a\), \(p\) and \(q\), determine whether \(\left(U_n\right)_{n \in \mathbb{N}}\) is a sequence of natural numbers, if not, find the index of the first term of the sequence that's not a natural number.

Input

The input contains three integers \(1 \leq a,p,q \leq 10^{12}.\)

Output

If \(\left(U_n\right)_{n \in \mathbb{N}}\) is an integer sequence, print \(\text{-1}\). Otherwise print the index of the first term of the sequence that's not an integer.

Examples

input1

1 3 4

output1

input2

2 3 1

output2

-1

input3

512 946 16