For a positive integer nn, let's denote function f(n,m)f(n,m) as the mm-th smallest integer xx that x>nx>n and gcd(x,n)=1gcd(x,n)=1. For example, f(5,1)=6f(5,1)=6 and f(5,5)=11f(5,5)=11.
You are given the value of mm and (f(n,m)−n)⊕n(f(n,m)−n)⊕n, where ``⊕⊕'' denotes the bitwise XOR operation. Please write a program to find the smallest positive integer nn that (f(n,m)−n)⊕n=k(f(n,m)−n)⊕n=k, or determine it is impossible.
Input
The first line of the input contains an integer T(1≤T≤10)T(1≤T≤10), denoting the number of test cases.
In each test case, there are two integers k,m(1≤k≤1018,1≤m≤100)k,m(1≤k≤1018,1≤m≤100).
Output
For each test case, print a single line containing an integer, denoting the smallest nn. If there is no solution, output ``-1-1'' instead.