NPC2015E - Eefun Plays LOL

Palkia is playing a popular game called "Lol of Legend". In that game, each player controls 1 champion where each champion has a finite number of skills. These skills can be used to empower other champions.

The main objective of this game is to defeat the enemies with these champions. However, one of Palkia's team member, Eefun, is unable to do that. Eefun only try to make his champions powerful.

Palkia angrily smashes the world where Eefun live with his superpower. Eefun is now stranded in NLC world and he meets Elsee. It turns out that the people of NLC world like playing with riddles and logic puzzles. Long story short, Eefun entered a logic contest and reach the finals. In the finals, Eefun has to solve this problem:

Elsee's father has a quite large coconut farm. The coconuts in this farm have different durabilities. Durability is determined by how high the coconut can be dropped without breaking. If a coconut has 50 durability, then it will break if dropped from 51 height. But, the coconut will not break or damaged if dropped from 50 height. Each coconut has a minimum of 0 and maximum of 2014 durability. Elsee is given two coconuts with the same durability by his father, however Elsee doesn't know their durabilities. Elsee wants to test the durability by dropping them from the window of a building. Worst case scenario, what is the minimum number of times Elsee need to drop the coconuts to know their durabilities? The building Elsee in has a height of 2014.

Eefun can't answer the question so he is eliminated. After the contest, Eefun got the solution from Elsee, which is 63. Eefun is determined to win the logic contest one day.

Palkia is feeling bad after what he's done, then he find another world that is similar to the previous world he destroyed, and he returned every inhabitant from the previous world to that new world. Eefun is sad because he can no longer enter the logic contest in NLC world. Eefun does not want his friendship with Elsee goes to waste so he created programming problem based on the problem that stumped him. Eefun then submits his problem to a programming contest and that problem is used in the contest. Here is the prolem:

Elsee's father has a quite large coconut farm. The coconuts in this farm have different durabilities. Durability is determined by how high the coconut can be dropped without breaking. If a coconut has 50 durability, then it will break if dropped from 51 height. But, the coconut will not break or damaged if dropped from 50 height. Each coconut has a minimum of 0 and maximum of N durability. Elsee is given K coconuts with the same durability by his father, however Elsee doesn't know their durabilities. Elsee wants to test the durability by dropping them from the window of a building. Worst case scenario, what is the minimum number of times Elsee need to drop the coconuts to know their durabilities? The building Elsee in has a height of N.

Input

First line of input contains a number T, the number of test cases. Next T lines each contains N and K, the maximum durability and number of coconuts.

Output

For each test case, output the minimum number of drop test that Elsee must do to find out the coconuts durability.

Example

Input:
3
100 2
2014 2
100000 1  Output: 14
63
100000 

For all subtask

  • 1 ≤ T ≤ 100000

Subtask 1:(10 points)

  • 1 ≤ N ≤ 1018
  • 1 ≤ K ≤ 2
  • Randomly generated

Subtask 2:(30 points)

  • 1 ≤ N ≤ 1000
  • 1 ≤ K ≤ 1000

Subtask 3:(60 points)

  • 1 ≤ N ≤ 1018
  • 1 ≤ K ≤ 1018

If you encounter a bug with the custom judge, please let me know in the comment.


Added by:Louis Arianto
Date:2015-10-10
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY
Resource:NPC Schematics 2015

hide comments
2021-05-06 11:29:25
Could someone give me very large input and output data?
2016-01-07 09:56:52 [Rampage] Blue.Mary
Be careful with 64-bit integer. Watch out for overflow problem.
2015-11-29 01:59:18 ivanilos
Time Limit seems too strict as I had to tweak a bit my code to get AC. Or did I need to optimize more the idea to solve the problem?
2015-10-28 11:46:56 Andy
@Bhargav
You need 100 points to get accepted, the scoring is there so you get a general idea which case your code fails. Your code throws an std::bad_alloc exception, causing a SIGABRT.
2015-10-28 02:49:14 Bhargav Golla
Could you check why 15486724 is throwing a SIGABRT? And also, what are these Subtask points? How do they work?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.