Segment Tree

题号：NC237296
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

Once upon a time, there was a segment tree of size $m$ .

You need to insert $k$ times in this segment tree.

Construct the array $P_0,P_1,\cdots,P_{k-1}$ so that the value of cnt is maximum cnt after finishing all the operations.

The first line contains a single integer $T$ $(1\le T\le 5\times 10^5)$ - the number of test cases.

For each next $T$ line, it contains two positive integers $m,q$ $(1\le m,q\le 10^{9})$ - the size of the segment tree and the number of operations.

For each test case, output a single integer represents the answer - the maximum cnt you can get.

示例1

复制

5
3 2
4 1
18 7
262144 65536
200000000 2262300

复制