# B. New Job

time limit per test：1 second

memory limit per test：64 megabytes

input：standard input

output：standard output

This is the first day for you at your new job and your boss asks you to copy some files from one computer to other computers in an informatics laboratory. He wants you to finish this task as fast as possible. You can copy the files from one computer to another using only one Ethernet cable. Bear in mind that any File-copying process takes one hour, and you can do more than one copying process at a time as long as you have enough cables. But you can connect any computer to one computer only at the same time. At the beginning, the files are on one computer (other than the computers you want to copy them to) and you want to copy files to all computers using a limited number of cables.

Input

First line of the input file contains an integer T (1  ≤  T  ≤  100) which denotes number of test cases. Each line in the next T lines represents one test case and contains two integers N, M.

N is the number of computers you want to copy files to them (1  ≤  N  ≤  1,000,000,000). While M is the number of cables you can use in the copying process (1  ≤  M  ≤  1,000,000,000).

Output

For each test case, print one line contains one integer referring to the minimum hours you need to finish copying process to all computers.

Examples

Input

3
10 10
7 2
5 3

Output

4
4
3

Note

In the first test case there are 10 computer and 10 cables. The answer is 4 because in the first hour you can copy files only to 1 computer, while in the second hour you can copy files to 2 computers. In the third hour you can copy files to 4 computers and you need the fourth hour to copy files to the remaining 3 computers.

1 #include <bits/stdc++.h>
2 using namespace std;
3 typedef long long ll;
5 {
6     int x=0,f=1;
7     char ch=getchar();
8     while(ch<'0'||ch>'9')
9     {
10         if(ch=='-')
11             f=-1;
12         ch=getchar();
13     }
14     while(ch>='0'&&ch<='9')
15     {
16         x=x*10+ch-'0';
17         ch=getchar();
18     }
19     return x*f;
20 }
21 inline void write(int x)
22 {
23     if(x<0)
24     {
25         putchar('-');
26         x=-x;
27     }
28     if(x>9)
29     {
30         write(x/10);
31     }
32     putchar(x%10+'0');
33 }
34 inline ll gcd(ll x,ll p,ll mod)
35 {
36     ll cnt=1;
37     for(;p;p>>=1,x=x*x%mod)
38     {
39         if(p&1)
40             cnt=cnt*x%mod;
41     }
42     return cnt;
43 }
44 ll n,m;
45 int main()
46 {
47     int t;
49     while(t--)
50     {
51         ll ans=0;
54         ll tim=1;
55         while(1)
56         {
57             if(tim>=m)
58             {
59                 tim=m;
60                 ans+=(n/tim);
61                 if(n%tim)
62                    ans++;
63                 break;
64             }
65             ans++;
66             n-=tim;
67             tim=tim*2;
68             if(n<=0)
69                break;
70         }
71         cout<<ans<<endl;
72     }
73     return 0;
74 }

0 条评论

## 相关文章

1292

### OFTest(一)：如何忽略一些字段在端口poll报文

1 前言 ✔ 关于OFTest的介绍，请戳这里(https://github.com/floodlight/oftest) ✔ 总的来说，就是用python写的...

3709

### 10:判决素数个数

10:判决素数个数 查看 提交 统计 提问 总时间限制: 1000ms 内存限制: 65536kB描述 输入两个整数X和Y，输出两者之间的素数个数（包括X和Y...

3876

1264

1885

851

### 网络后台开发面试题

1.C++模板的作用。 将算法与具体对象分离，与类型无关，通用，节省精力 2.socket编程，如果client断电了，服务器如何快速知道？？？ 有以下几个...

6538

2255

1512

2088