High-Precision M-base Calculator

You are given a high-precision calculator that works in base M. The display initially shows the number 1. Every time you press the button, the number on the display is multiplied by K. The door will open when the last digit (the units digit in base M) becomes 1 again.

Your task is to calculate the minimum number of button presses needed so that the displayed number again ends with 1. In mathematical terms, find the smallest positive integer n such that:

$$K^n \equiv 1 \pmod{M}.$$

If no such positive integer exists, output -1.

inputFormat

The input consists of a single line containing two space-separated integers:

• M (the base of the calculator)
• K (the multiplier for each button press)

outputFormat

Output a single integer representing the minimum number of button presses required so that the last digit in the base-M representation becomes 1 again. If it is impossible, output -1.

sample

5 2

4