Description

Define：An = X*An-1 + Y

and Y mod (X-1) = 0.

Your task is to calculate the smallest positive integer k that Ak mod A0 = 0.

Input

Each line will contain only three integers X, Y, A0 ( 1 < X < 2^31, 0 <= Y < 2^63, 0 < A0 < 2^31).

Output

For each case, output the answer in one line, if there is no such k, output "Impossible!".

Sample

Input

2 0 9

Output

1

Source: zjut_DD