Description

求关于x的同余方程ax≡ 1(mod b)的最小正整数解。

Input Format

输入只有一行，包含两个正整数a，b,用一个空格隔开.

Output Format

输出只有一行，包含一个正整数x0，即最小正整数解。输入数据保证一定有解。

Sample

输入

3 10

输出

7

Hint

对于 40% 的数据，有 2=<b<=1000；

对于 60% 的数据，有 2=<b<=50000000；

对于 100% 的数据，有2=<b<=2000000000 。