좋은 비트열

양의 정수 $a$와 $b$에 대해 함수 gen_string(a,b)는 다음 Python 코드로 정의한다.

def gen_string(a: int, b: int):
	res = ""
	ia, ib = 0, 0
	while ia + ib < a + b:
		if ia * b ≤ ib * a:
			res += '0'
			ia += 1
		else:
			res += '1'
			ib += 1
	return res

같은 동작을 하는 C++ 코드는 다음과 같다.

string gen_string(int64_t a, int64_t b) {
	string res;
	int ia = 0, ib = 0;
	while (ia + ib < a + b) {
		if ((__int128)ia * b ≤ (__int128)ib * a) {
			res += '0';
			ia++;
		} else {
			res += '1';
			ib++;
		}
	}
	return res;
}

루프가 끝나면 $ia$는 $a$와 같고 $ib$는 $b$와 같아진다. 따라서 이 함수는 길이가 $a+b$이고, 0이 정확히 $a$개, 1이 정확히 $b$개인 비트열을 반환한다. 예를 들어 gen_string(4,10)=01110110111011이다.

비트열 $s$에 대해 양의 정수 $x$, $y$가 존재하여 $s$ = gen_string($x$,$y$)이면 $s$를 좋은 비트열이라 한다. 양의 정수 $A$, $B$ ($1 \le A, B \le 10^{18}$)가 주어지면 gen_string($A$,$B$)의 좋은 접두사의 개수를 구하라.

예를 들어 gen_string(4,10)의 좋은 접두사는 6개이다.

x = 1 | y = 1 | gen_string(x, y) = 01
x = 1 | y = 2 | gen_string(x, y) = 011
x = 1 | y = 3 | gen_string(x, y) = 0111
x = 2 | y = 5 | gen_string(x, y) = 0111011
x = 3 | y = 7 | gen_string(x, y) = 0111011011
x = 4 | y = 10 | gen_string(x, y) = 01110110111011

첫 줄에 테스트 케이스의 수 $T$ ($1 \le T \le 10$)가 주어진다. 이후 $T$개의 줄에 각각 두 정수 $A$와 $B$가 주어진다.

각 테스트 케이스의 답을 한 줄에 하나씩 출력한다.