4852: [NOIP2012 提高组] 同余方程

Memory Limit:128 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:8 Solved:2

Description

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


Input

一行,包含两个整数 ,,用一个空格隔开。


Output


一个整数 0,即最小正整数解。输入数据保证一定有解。




Sample Input Copy

3 10

Sample Output Copy

7

HINT

数据规模与约定

  • 对于 40% 的数据,21,000
  • 对于 60% 的数据,250,000,000
  • 对于 100% 的数据,2,2,000,000,000