In the lab, Jesse & Heisenberg were experimenting with some formulas that they made for synthesizing their product. To come up with a new product, Heisenberg arranged different molecular weights which are integers in the form of a series. The resulting series goes like -

1,1,2,3,5,8,13....

"Yo, Mr. White! I don't understand any damn thing."

"Just do as I say, Jesse. This is how things work in science."

In order to synthesize a new product, Heisenberg needs to find out HCF (Highest Common Factor) of given two terms from the series modulo 10⁹+7.

He gives this job to Jesse, and asks him to complete this as soon as possible. Jesse has no clue about the series, so he wants your help.

"Yo, Help me out bro!"

INPUT

• First line contains an integer T, the number of Test Cases.
• Next T lines contains two space separated integers M and N in each line

OUTPUT

• Output should contain exactly T lines. Each line containing the answer (HCF of the M^th & N^th term of the series modulo 10⁹+7).

CONSTRAINTS

• 1 ≤ T ≤ 100000
• 1 ≤ M,N ≤ 10⁶