累加器
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

存在一个累加器,每次可以对一个数进行加 1 操作,此时在二进制下有一些位发生改变,对一个数 x 进行 y 次累加操作,总共有多少位发生改变。

输入描述:

第一行一个正整数 T (1\leq T \leq 10^5)代表多组询问。

接下来 T 行 每行两个正整数 x,y(1\leq x,y \leq 10^6),代表对 x 进行 y 次累加操作。

输出描述:

T 行每组询问一行代表总共发生改变的位数。
示例1

输入

复制
4
1 4
10 1
20 20
1 100

输出

复制
7
1
40
197

说明

对于第一个样例开始 (0001)_2 进行 4 次累加。

第一次 (0010)_2 两位改变。

第二次 (0011)_2 一位改变。

第三次 (0100)_2 三位改变。

第四次 (0101)_2 一位改变。

备注: