链接：

来源：牛客网

题目描述

uu遇到了一个小问题，可是他不想答。你能替他解决这个问题吗？

问题：给你k对a和r是否存在一个正整数x使每队a和r都满足：x mod a=r，求最小正解x或无解。

输入描述:

第一行是正整数k(k<=100000) 接下来k行，每行有俩个正整数a，r(100000>a>r>=0)

输出描述:

在每个测试用例输出非负整数m，占一行。 如果有多个可能的值，输出最小的值。 如果没有可能的值，则输出-1。

示例1

输入

28 711 9

输出

31

#include
          
           using namespace std; long long a[100006],m[100006]; void ex(long long b,long long c,long long &d,long long int &x,long long int &y){    if(!c){        d=b; x=1; y=0;    }    else{        ex(c,b%c,d,y,x);        y-=x*(b/c);    }} long long china(int n){    long long m1,r1;    m1=a[0],r1=m[0];    for(int i=1;i
          

　　运用扩展欧几里得算法求出乘法逆元，逆元乘上除数相加。