一个小问题
题号:NC15068
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 32 M,其他语言64 M
64bit IO Format: %lld

题目描述

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

输入

复制
2
8 7
11 9

输出

复制
31