Naruto is in the middle of the fight and his present power is p. He uses Tajū Kage Bunshin no Jutsu (Multiple Shadow Clone Technique) to create maximum n number of clones and he decided to distribute maximum p/2 power to the possible number of clones. First clone will always receive power equal to 1 and i th clone will receive power as i th term of an AP starting with 1 and having sum less than equal to p/2. Now he sends all even clones for observation and odd ones for fighting. After the battle is over only the observation clones and the highest power clone is alive. What is Naruto's power after he call back all his clones?

Input

The first line contains the number of test cases t (t <= 1000). The next following t lines will contain two integers p and n (1 <= p, n <= 10^9).

Output

Output must contains t lines consisting of the answer as mentioned in above question.

Example

Input:
1
200 10

Output:
155

Explanation:- Naruto is going to give 100 power to 10 clones. So there will be an AP with first term as 1 common difference 2. On adding required terms we get 55, and hence total power is 155.