**Problem**

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**

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.

**Output**

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

**Sample Input**

1

3 6

**Sample Output**

3

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

Author: