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, F = 1, F = 2 , F = 3, F = 5, F = 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,F,F.
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.
Notice: You should at least use scanf to read data!