题目描述

一轮正在玩三国杀，他现在拿李傕跟别人单挑，李傕有 $a$ 点血，对方有 $b$ 点血，李傕每回合都可以给对方造成随机整数点伤害，对方则每回合都可以给李傕造成对方的当前血量数量的伤害数。当一方的回合造成的伤害大于等于另一方的血量时，游戏结束，前者获得胜利。

游戏开始时一轮先手。他们总共会进行 $n$ 轮游戏，请你告诉一轮每一轮他每回合最少要造成多少点伤害才能保证他这一轮一定获得胜利。

输入格式

第一行一个整数 $n$。

接下来 $n$ 行，每行包含两个正整数 $a$ 和 $b$，表示一轮的血量和对方的血量。

输出格式

共 $n$ 行，每行输出对应答案，表示最少伤害。

3
4 3
13 4
20 15

1
1
5

解释 #1

李傕血量为 4，对方血量为 3

李傕造成 1 点伤害，对方血量变为 2。

对方造成 2 点伤害，李傕血量变为 2。

李傕造成 1 点伤害，对方血量变为 1。

对方造成 1 点伤害，李傕血量变为 1。

李傕造成 1 点伤害，对方血量变为 0。

所以 1 点伤害就可以保证一轮一定获得胜利。

数据范围

$1\le n \le 10^5$。

$1\le a \le 10^{18}，1 \le b\le 10^9，b \le a$。