Maximise Set Bits

 Let [Math Processing Error]

$f(X)$ denote the number of set bits in [Math Processing Error]$X$.

Given integers [Math Processing Error]$N$ and [Math Processing Error]$K$, construct an array [Math Processing Error]$A$ of length [Math Processing Error]$N$ such that:

• [Math Processing Error]$0\le A_i\le K$ for all [Math Processing Error]$(1\le i\le N)$;
• [Math Processing Error]$\sum _{i=1}^N{A}_i=K$

Over all such possible arrays, find the maximum value of [Math Processing Error]$\sum _{i=1}^{N}f(A_i)$.

Input Format

• The first line of input contains a single integer [Math Processing Error]$T$ - the number of test cases. The description of [Math Processing Error]$T$ test cases follow.
• The only line of each test case contains integers [Math Processing Error]$N$ and [Math Processing Error]$K$- the length of the array and sum of elements respectively.

Output Format

For each test case, output the maximum value of [Math Processing Error]$\sum _{i=1}^{N}f(A_i)$.

Constraints

• [Math Processing Error]$1\le T\le {10}^4$
• [Math Processing Error]$1\le N\le {10}^9$
• [Math Processing Error]$0\le K\le {10}^9$

Sample Input 1 

2
1 7
3 6

Sample Output 1 

3
4

Explanation

Test case [Math Processing Error]$1$: Only one array is possible that is [Math Processing Error]$A=[7]$. As [Math Processing Error]$7=(111{)}_2$, the number of set bits in [Math Processing Error]$7$ is [Math Processing Error]$3$. Thus, [Math Processing Error]$\sum _{i=1}^{N}f(A_i)=f(7)=3$.

Test case [Math Processing Error]$2$: A possible array satisfying all the conditions is [Math Processing Error]$A=[3,0,3]$. As [Math Processing Error]$3=(11{)}_2$, the number of set bits in [Math Processing Error]$3$ is [Math Processing Error]$2$. Similarly, the number of set bits in [Math Processing Error]$0$ is [Math Processing Error]$0$. Thus, [Math Processing Error]$\sum _{i=1}^{N}f(A_i)=f(3)+f(0)+f(3)=4$. It can be proven that answer never exceeds [Math Processing Error]$4$.