Broken Calculator#817
The calculator has two memory cells: the content of the first cell is always displayed on the screen, and the second cell acts as a buffer. Initially, the screen shows the integer , and the buffer contains . The calculator has only two working buttons: «+» and «=». When «+» is pressed, the number currently displayed on the screen is copied into the buffer. When «=» is pressed, the number from the buffer is added to the number on the screen, the result is displayed on the screen, and the buffer's content does not change.
Determine the minimum number of button presses required to display the number on the screen.
The input file contains two integers and . Each of these numbers does not exceed 10^9 in absolute value.
Output a single integer: the minimum number of button presses needed to obtain the number . If it is impossible to obtain from using the given operations, output .
Example 1