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.