It’s the Valentines Day i.e. 14^th Feb and many girls of IIT Mandi are excited about it. They all want to propose our very own handsome, smart and intelligent Acad Secy Abhishek 'Keval' Sharma. One of the girl approached him but our Acad Secy doesn’t seems to be desperate. He’ll accept the proposal only if she solves the problem given by him. As she is not quite good in maths :(, you being her best friend ;) , she asks your help. Can you help her solve the problem?

There is an array of N distinct positive integers. The integers are in the range A to A+N-1. She has to find the GCD of all the integers in this array. But instead of the whole array you are just given the value of A and N.

Input

The first line contains the total number of test cases T. Each of the test case contains two space-separated positive integers A and N.

Output

For each test cases print the answer in a single line.

Constraints

• 1 <= T <= 10
• 1 <= A,N <= 10⁵⁰

Subtasks

Subtask #1 (40 points):

• 1 <= A,N <= 10⁵

Subtask #2 (60 points):

• Original Constraints