Saraff is planning to open a general store in his locality. He is planning to buy a weight balance and some weights to measure weights in the store.
There is a single store Pahi's Weight Store which sells balance and weights in Saraff's country. Pahi's store has K pieces of each positive integral weight and buying all K pieces of a weight costs 1 Rupee. For each integral weight, you can either not take it, or take K pieces of it and pay 1 Rupee.
Saraff wants to find what minimum amount of money he needs to spend so that he is able to measure all the positive integral weights \(\le N\). To measure a weight X, he needs some pieces such that the sum of their values equals X.
INPUT CONSTRAINTS
- \(1 \le T \le 10^5\)
- \(1 \le K \le 10^6\)
- \(1 \le N \le 10^{18}\)
INPUT FORMAT
First line of input contains a single integer T, denoting number of test case. Each test case contains two space separated integers K and N.
OUTPUT FORMAT
Print the minimum amount of money he needs to spend so that Saraff is able to measure all the positive integral weights \(\le N\). To measure a weight X, he needs some pieces such that the sum of their values equals X.
1 1 5
3
Buying weights of 1 kg, 2 kg and 3 kg will give Saraff 1 weight of each of them.
To weigh 1 kg : He can use a single 1 kg weight.
To weigh 2 kg : He can use a single 2 kg weight.
To weigh 3 kg : He can use a single 3 kg weight.
To weigh 4 kg : He can use a 1 kg weight and 3 kg weight.
To weigh 5 kg : He can use a 2 kg weight and 3 kg weight.
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
Login to unlock the editorial
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