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 ≤N. To measure a weight X, he needs some pieces such that the sum of their values equals X.
INPUT CONSTRAINTS
- 1≤T≤105
- 1≤K≤106
- 1≤N≤1018
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 ≤N. To measure a weight X, he needs some pieces such that the sum of their values equals X.
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.
