This is the hardest one of this series. So, make your algorithm fantastic enough ^_^

First, let's define Fibonacci Common Divisor(FCD):

Suppose F is a Fibonacci sequence, F[1] = 1, F[2] = 1, F[3] = 2 , F[4] = 3, F[5] = 5, F[6] = 8, ......

If F[k] | F[i] and F[k] | F[j], we say F[k] is the FCD of F[i] and F[j].

Given two positive integers i and j, you are to tell the FCD number of F[i] and F[j].
For example, i = 3, j = 6; F[i] and F[j] have 3 FCD, they are F[1],F[2],F[3].
It is guaranteed that no FCD of F[i] and F[j] will be larger than 0.1953584078e208988 in the input.


Input contains multiple test cases. The first line of the input is an integer T (T <= 1,000,000) representing the number of test cases, followed by T lines, each line contains two positive integers i,j.


For each test case, print the total number of FCD.

Sample Input

3 6

Sample Output


Notice: You should at least use scanf to read data!

Author: Wiltord Gun