Algorithm

A. C+=
time limit per test
2 seconds
memory limit per test
512 megabytes
Problem link- https://codeforces.com/problemset/problem/1368/A
input
standard input
output
standard output

Leo has developed a new programming language C+=. In C+=, integer variables can only be changed with a "+=" operation that adds the right-hand side value to the left-hand side variable. For example, performing "a += b" when a = 22, b = 33 changes the value of a to 55 (the value of b does not change).

In a prototype program Leo has two integer variables a and b, initialized with some positive values. He can perform any number of operations "a += b" or "b += a". Leo wants to test handling large integers, so he wants to make the value of either a or b strictly greater than a given value n�. What is the smallest number of operations he has to perform?

Input

The first line contains a single integer T� (1≤T≤1001≤�≤100) — the number of test cases.

Each of the following T� lines describes a single test case, and contains three integers a,b,n�,�,� (1≤a,b≤n≤1091≤�,�≤�≤109) — initial values of a and b, and the value one of the variables has to exceed, respectively.

Output

For each test case print a single integer — the smallest number of operations needed. Separate answers with line breaks.

Example
input
Copy
2
1 2 3
5 4 100
output
Copy
2
7
Note

In the first case we cannot make a variable exceed 33 in one operation. One way of achieving this in two operations is to perform "b += a" twice.

 



 

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming

#includ<bits/stdc++.h>
using namespace std;


#define ll long long
#define endl '\n'
#define debug(n) cout<<(n)<<endl;
const ll INF = 2e18 + 99;

int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);

  int t;
  cin>>t;
  while(t--){
    int a, b, n;
    cin>>a>>b>>n;
    if(b < a){
      int temp = a;
      a = b;
      b = temp;
    }
    int count = 0;

    while(a <= n && b <= n){
      if(a <= n){
        a += b;
        count++;
      }
      if(a > n){
        break;
      }

      if(b <= n){
        b += a;
        count++;
      }
      if(b > n){
        break;
      }

    }
    cout<<count<<endl;
  }

}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
2
1 2 3
5 4 100

Output

x
–
+
cmd
2
7
Advertisements

Demonstration

Codeforcess solution 1368-A  A. C+= ,C++, Java, Js and Python,1368-A,Codeforcess solution

Previous
Codeforces solution 1080-B-B. Margarite and the best present codeforces solution
Next
CodeChef solution DETSCORE - Determine the Score CodeChef solution C,C+