又一道 Popcount 问题

英文题名：A. Another Popcount Problem
来源：Codeforces 2240A
比赛：Codeforces Round 1105 (Div. 2)
时间限制：1 second
空间限制：256 megabytes

题目描述

给定 $n,k$，构造 $k$ 个非负整数且总和不超过 $n$，最大化这些数的二进制 $1$ 的总个数。只需输出最大值。

输入格式

第一行输入 $t$。每组输入 $n,k$。

输出格式

每组输出最大 popcount 总和。

样例

6
2 1
3 1
6 2
14142 137205
1000000 100
1000000 1000000

1
2
4
14142
1322
1000000