l--互质数

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

给出2个数M和N(M < N),且M与N互质,找出一个数K满足0 < K < N且K * M % N = 1,如果有多个满足条件的,输出最小的。

Input

输入2个数M, N中间用空格分隔(1 <= M < N <= 10^9)

Output

 输出一个数K,满足0 < K < N且K * M % N = 1,如果有多个满足条件的,输出最小的。

Sample Input

2 3

Sample Output

2

Hint

 互质数:公因数只有1的两个数,叫做互质数。(不算它本身)例如:2和3,3和5,公因数只有1,为互质数。

Source

Rocky