Jesse & Heisenberg's Experiment
Practice
2 (5 votes)
Easy Medium
Problem
82% Success 3221 Attempts 30 Points 5s Time Limit 256MB Memory 1024 KB Max Code

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."

enter image description here

In order to synthesize a new product, Heisenberg needs to find out HCF (Highest Common Factor) of given two terms from the series modulo 109+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 Mth & Nth term of the series modulo 109+7).

CONSTRAINTS

  • 1 ≤ T ≤ 100000
  • 1 ≤ M,N ≤ 106

Please login to use the editor

You need to be logged in to access the code editor

Loading...

Please wait while we load the editor

Loading...
Results
Custom Input
Run your code to see the output
Submissions
Please login to view your submissions
Similar Problems
Points:30
21 votes
Tags:
SortingIntegerModulus ArithmeticModulesC++Number TheoryMathematics
Points:30
3 votes
Tags:
MathematicsModular arithmeticEasy-Medium
Points:30
13 votes
Tags:
MathematicsModular arithmeticEasy-Medium