We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • Hackerrank Home
  • Prepare
    NEW
  • Certify
  • Compete
  • Career Fair
  • Hiring developers?
  1. All Contests
  2. ProjectEuler+
  3. Project Euler #115: Counting block combinations II

Project Euler #115: Counting block combinations II

Problem
Submissions
Leaderboard
Discussions

This problem is a programming version of Problem 115 from projecteuler.net

A row measuring units in length has red blocks with a minimum length of units placed on it, such that any two red blocks (which are allowed to be different lengths) are separated by at least one black square.

Let the fill-count function, , represent the number of ways that a row can be filled.

For example, and .

That is, for , it can be seen that is the smallest value for which the fill-count function first exceeds one million.

In the same way, for , it can be verified that and , so is the least value for which the fill-count function first exceeds one million.

For given , find the least value of for which .

Input Format

First line contains an integer denoting the number of test cases.
Each of the following lines contain two integers and .

Constraints

Output Format

For each of test cases print one line containing a single integer - the answer to a problem.

Sample Input

2
3 1000000
10 1000000

Sample Output

30
57

Author

Alex_2oo8

Difficulty

Medium

Max Score

100

Submitted By

203

Need Help?


View discussions
View top submissions

rate this challenge

MORE DETAILS

Download problem statement
Download sample test cases
Suggest Edits
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy