You are given a fair coin and two integers X and N.

You repeatedly flip the coin and perform the following operation based on the result:
If it lands on heads, then X will increase by 1. However, if X = N then X will not change.
If it lands on tails, X will decrease by 1.

You stop as soon as the value of X becomes 1.

Find the expected number of coin flips.

Note that it is guaranteed that under the given constraints, the answer is an integer and does not exceed 2 \cdot 10^{18}

------ Input Format ------ 

- The first line contains a single integer T — the number of test cases. Then the test cases follow.
- The first and only line of each test case contains two space separated integers X and N.

------ Output Format ------ 

For each testcase, output the expected number of coin flips.

------ Constraints ------ 

$1 ≤ T ≤ 10^{5}$
$1 ≤ X ≤ N ≤ 10^{9}$

----- Sample Input 1 ------ 
4
1 3
2 2
12 12
568 57800
----- Sample Output 1 ------ 
0
2
132
65223144

----- explanation 1 ------ 
In the first test case, $X$ is already $1$. So, the expected number of coin flip in this case is $0$.

In the second test case, if the coin lands on head, $X$ will not change because $X$ is equal to $N$ here. Whenever the coin lands on tail, $X$ will decrease by $1$ and the game ends as $X$ becomes $1$. The expected number of coin flips to get the first tail is $2$. So, the answer for the case is $2$.

Difficulty: MEDIUM
Tags: Mathematics

Probability

Starter code:

Solutions:
t = int(input())
for _ in range(t):
	(x, n) = map(int, input().split())
	print((x - 1) * (2 * n - x))


for i in range(int(input())):
	(x, n) = map(int, input().split())
	if x == n:
		print((x - 1) * n)
	else:
		print(2 * (x - 1) * n - (x - 1) * x)


for i in range(int(input())):
	(X, Y) = map(int, input().split())
	if X == 1:
		print(0)
	else:
		print((X - 1) * (2 * Y - X))


for i in range(int(input())):
	l = list(map(int, input().split()))
	if l[0] == 1:
		print(0)
	elif l[0] == l[1]:
		c = l[0] - 1
		d = c * l[1]
		print(d)
	elif l[0] < l[1]:
		c = l[0] - 1
		d = c * (2 * l[1] - l[0])
		print(d)


for _ in range(int(input())):
	(x, n) = map(int, input().split())
	if x == 1:
		print(0)
	elif x == n:
		print((x - 1) * n)
	elif x < n:
		print((x - 1) * (2 * n - x))


a = int(input())
for i in range(a):
	b = [int(j) for j in input().split()]
	if b[0] == 1:
		print(0)
	elif b[0] == b[1]:
		c = b[0] - 1
		d = c * b[1]
		print(d)
	elif b[0] < b[1]:
		c = b[0] - 1
		d = c * (2 * b[1] - b[0])
		print(d)


import random
t = int(input())
for i in range(t):
	(s, count) = (0, 0)
	(x, n) = map(int, input().split())
	if x == 1:
		print('0')
	else:
		count = (x - 1) * (2 * n - x)
		print(count)


T = int(input())
for i in range(T):
	(X, N) = map(int, input().split())
	print((X - 1) * (2 * N - X))


t = int(input())
while t:
	str_arr = input().split(' ')
	arr = [int(num) for num in str_arr]
	(x, n) = (arr[0], arr[1])
	print((x - 1) * (n * 2 - x))
	t -= 1


T = int(input())
for i in range(T):
	ding = input()
	ding = ding.split()
	X = int(ding[0]) - 1
	N = int(ding[1]) - 1
	flips = N * (N + 1) - (N - X) * (N - X + 1)
	print(flips)


import random
for _ in range(int(input())):
	(x, n) = map(int, input().split())
	print((x - 1) * (2 * n - x))


t = int(input())
for _ in range(t):
	(a, b) = [int(p) for p in input().split()]
	print((a - 1) * (2 * b - a))


for i in range(int(input())):
	(a, b) = [int(p) for p in input().split()]
	print((a - 1) * (2 * b - a))


for _ in range(int(input())):
	(x, n) = list(map(int, input().split()))
	ans = (x - 1) * (2 * n - x)
	print(ans)


for _ in range(int(input())):
	(x, y) = map(int, input().split())
	print((x - 1) * (2 * y - x))


for i in range(int(input())):
	(a, b) = map(int, input().split())
	if a == 1:
		print('0')
	elif a == b:
		c = a * b
		c = c - a
		print(c)
	else:
		d = abs(a - b)
		d = d + b
		e = d
		d = d * a
		d = d - e
		print(d)


t = int(input())
for j in range(t):
	(x, n) = map(int, input().split())
	if x == 1:
		print(0)
	else:
		print((x - 1) * (2 * n - x))


t = int(input())
for _ in range(t):
	res = 0
	(a, b) = map(int, input().split())
	if a == 1:
		print(0)
	else:
		res = (a - 1) * (2 * b - a)
		print(res)


k = int(input())
for i in range(k):
	(a, b) = map(int, input().split())
	print((a - 1) * (2 * b - a))


for _ in range(int(input())):
	(X, N) = list(map(int, input().split()))
	ans = (X - 1) * (2 * N - X)
	print(ans)


from math import ceil
for i in range(int(input())):
	(n, x) = map(int, input().split())
	ans = (n - 1) * x * 2
	ans -= n * (n - 1)
	print(ans)


def expMove(x, n):
	print((x - 1) * (2 * n - x))
T = int(input())
while T:
	(X, N) = map(int, input().split())
	expMove(X, N)
	T -= 1


t = int(input())
while t > 0:
	t -= 1
	(x, n) = input().split()
	x = int(x)
	n = int(n)
	b = x - 1
	if x - 1 == 0:
		print(0)
	else:
		print((2 * n - x) * b)


T = int(input())
for i in range(T):
	(X, N) = [int(x) for x in input().split()]
	result = int(0)
	c = 2 * N - X
	d = X - 1
	result = c * d
	print(result)


t = int(input())
for i in range(t):
	(x, n) = map(int, input().split())
	s = (x - 1) * (n * 2 - x)
	print(s)


t = int(input())
while t > 0:
	(x, n) = input().split()
	x = int(x)
	n = int(n)
	print((x - 1) * (2 * n - x))
	t = t - 1


T = int(input())
for i in range(T):
	(A, B) = map(int, input().split())
	if A == 1:
		print('0')
	else:
		print((A - 1) * (2 * B - A))


t = int(input())
for i in range(t):
	(a, b) = map(int, input().split())
	n = (a - 1) * (b * 2 - a)
	print(n)


try:
	for k in range(int(input())):
		(A, B) = map(int, input().split())
		j = 0
		j = (A - 1) * (2 * B - A)
		print(j)
except:
	pass


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	print((a - 1) * (2 * b - a))


for _ in range(int(input())):
	p = list(map(int, input().split()))
	x = (p[0] - 1) * (2 * p[1] - p[0])
	print(x)


n_tc = input()
for i in range(int(n_tc)):
	alp = [int(item) for item in input().split()]
	x = alp[0]
	y = alp[1]
	print((x - 1) * (2 * y - x))


for _ in range(int(input())):
	(X, N) = map(int, input().split())
	if X == 1:
		print(0)
	else:
		print((X - 1) * (2 * N - X))


import math
t = int(input())
for i in range(t):
	(x, n) = map(int, input().split())
	if x == 1:
		print(0)
	elif x == n:
		print(n * n - n)
	else:
		print((x - 1) * (2 * n - x))


for i in range(int(input())):
	(x, n) = map(int, input().split())
	y = int(x - 1)
	z = int(2 * n - x)
	print(y * z)


for _ in range(int(input())):
	(a, b) = map(int, input().split(' '))
	if a == 1:
		print('0')
	else:
		s = (a - 1) * (2 * b - a)
		print(s)


import math
t = int(input())
while t:
	t -= 1
	(x, n) = map(int, input().split())
	s = (x - 1) * (2 * n - x)
	print(s)


for i in range(int(input())):
	(x, y) = map(int, input().split())
	if x == 1:
		print(0)
	else:
		s = (x - 1) * (2 * y - x)
		print(s)


def move():
	(x, n) = input().split()
	x = int(x)
	n = int(n)
	res = (x - 1) * (2 * n - x)
	print(res)
t = int(input())
while t:
	move()
	t -= 1


T = int(input())
for tc in range(T):
	(x, n) = map(int, input().split(' '))
	d = (x - 1) * (2 * n - x)
	print(d)


t = int(input())
for i in range(t):
	(x, n) = [int(i) for i in input().split()]
	ans = (x - 1) * (2 * n - x)
	print(ans)


import os.path
from math import gcd, floor, ceil, log2
from collections import *
import sys
mod = 1000000007
INF = float('inf')

def st():
	return list(sys.stdin.readline().strip())

def li():
	return list(map(int, sys.stdin.readline().split()))

def mp():
	return map(int, sys.stdin.readline().split())

def inp():
	return int(sys.stdin.readline())

def pr(n):
	return sys.stdout.write(str(n) + '\n')

def prl(n):
	return sys.stdout.write(str(n) + ' ')
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
for _ in range(int(input())):
	(x, n) = mp()
	print((x - 1) * (2 * n - x))


for _ in range(int(input())):
	(x, n) = map(int, input().split())
	if x == 1:
		print(0)
	else:
		dif = n - x
		m = n + dif
		x = x - 1
		print(x * m)


t = int(input())
while t > 0:
	(x, n) = map(int, input().split())
	a = (x - 1) * (2 * n - x)
	print(a)
	t -= 1


t = int(input())
for i in range(t):
	l = list(map(int, input().split()))
	(x, n) = (l[0], l[1])
	ans = (x - 1) * (2 * n - x)
	print(ans)


t = int(input())
for i in range(t):
	xn = input().split()
	x = int(xn[0])
	n = int(xn[1])
	print((x - 1) * (2 * n - x))


try:
	for i in range(int(input())):
		(x, n) = map(int, input().split())
		answer = (x - 1) * (2 * n - x)
		print(answer)
except:
	pass


t = int(input())
while t > 0:
	(x, y) = map(int, input().split())
	if x == 1:
		print(0)
	else:
		print((x - 1) * (2 * y - x))
	t -= 1


for _ in range(int(input())):
	(x, n) = input().split()
	x = int(x)
	n = int(n)
	count = (x - 1) * (2 * n - x)
	print(count)


try:
	for i in range(int(input())):
		(a, b) = map(int, input().split())
		print((a - 1) * (2 * b - a))
except:
	pass


testone = int(input())
for jkc in range(testone):
	(temp1, temp2) = map(int, input().split())
	a = temp1 - 1
	b = temp2 * 2 - temp1
	print(a * b)


mant = int(input())
while mant:
	(siva, visa) = map(int, input().split())
	kiss = 2 * visa * (siva - 1) - siva * (siva - 1)
	print(kiss)
	mant -= 1