How many non decreasing sequences are there of length , with the condition that numbers in sequence can take values only from and gcd of all numbers in the sequence must be .

Input Format
The first line contains an integer i.e. the number of test cases.
lines follow, each line containing two integers and separated by a single space.

Output Format
For each testcase, print in a newline the answer .

Constraints

Sample Input

4
2 4 
3 4
5 2
1 10

Sample Output

4
13
10
1

Explanation

For the first testcase, the sequences are

(1,1,1,1), (1,1,1,2), (1,1,2,2), (1,2,2,2) = 4

For the second testcase, the sequences are

(1,1,1,1), (1,1,1,2), (1,1,1,3), (1,1,2,2), (1,1,2,3), (1,1,3,3)
(1,3,3,3), (1,2,2,2), (1,2,2,3), (1,2,3,3), (2,2,2,3), (2,2,3,3), (2,3,3,3)

which are 13 in number.

For the third testcase, the sequences are

(1,1), (1,2), (1,3), (1,4), (1,5), (2,3), (2,5), (3, 4), (3, 5), (4, 5) = 10

for the fourth testcase, the only sequence is

(1,1,1,1,1,1,1,1,1,1)