407010: GYM102680 E Negigent Norbert

Naughty Negligent Norbert has been given a notoriously repetitive responsibility: answering the clarification requests for a programming competition! Norbert realizes that since all the questions are perfectly unambiguous, he doesn't really have to do his job, and the only reason he is responding to requests at all is so he can get service hours. The savvy programmers, however, have implemented a system to prevent Norbert from simply giving the same answer to all clarification requests.

Having seen the source code for the competition, Norbert knows that he will lose all his service hours for not doing his job correctly if any two of his responses are identical. Negligent Norbert decides that for each of his $$$T$$$ competitions, he will respond to the $$$q$$$ clarification requests using as few characters as possible. Also, because Norbert is very diverse and speaks many languages, he will answer all questions in a given competition using a language with $$$n$$$ characters. What is the fewest number of keystrokes Norbert can type in each competition to still get his service hours?

Each response must have at least 1 character, and responses do not necessarily all have to be the same length. Norbert will click the submit button with his mouse instead of pressing the return key, so the total number of keystrokes is the sum of the lengths of each response.

The first line will contain an integer $$$T$$$. $$$T$$$ lines follow, each containing two space-separated integers, $$$q$$$ and $$$n$$$, the number of clarification requests and the number of characters in the language for the current competition.

$$$1 \leq T \leq 100$$$

$$$1 \leq q \leq 10^{11}$$$

$$$2 \leq n \leq 10^5$$$

Output $$$T$$$ lines, each containing a single integer representing the number of characters in all of Norbert's responses for a competition.

3
7 3
5 26
14 3

11
5
27

For the first test case, Norbert is using a language with 3 characters, Norbert could answer, for example, AC, CA, A, BC, C, AA, and B, for a total character count of 2+2+1+2+1+2+1 = 11.

For the second test case, Norbert could answer each of the five clarification requests with a different character, using a total of 5 characters. So we output 5 on a new line.

For the third test case, Norbert will need to use all of the one-letter and two-letter words, and two more three-letter words, for a total of 27 characters.