Chef loves to play games. Now he plays very interesting game called "Segment". At the beginning Chef has segment [0, X] and no points on it. On each step Chef chooses the subsegment of maximal length possible such as it contains no points on it. If there are more than one such subsegment Chef chooses the one with the minimal left coordinate. Once Chef chosed the subsegment he put the point in it's middle and the step is over.
Help Chef to define the coordinate of the point he will put on the K-th step. 

-----Input-----
- The first line contains integer T - number of test cases. 
- Each of next T lines contains two integers X and K. 

-----Output-----
- For each test case in a single line print single double number - the coordinate of the K-th point Chef will put. Answer will be considered as correct if absolute difference between the answer and correct answer is less or equal 10^(-6). 

-----Constraints-----
- 1 ≤ T ≤ 10^5
- 1 ≤ X ≤ 10^9
- 1 ≤ K ≤ 10^12

-----Subtasks-----
- Subtask 1: T ≤ 10; X, K ≤ 20. Points: 15 
- Subtask 2: T ≤ 10; X ≤ 10^6, K ≤ 2*10^5. Points: 25
- Subtask 3: T ≤ 10^5; X ≤ 10^9, K ≤ 10^12. Points: 60

-----Example-----
Input:
4
10 1
10 2
10 3
1000000000 1234567
Output:
5.0000
2.5000
7.5000
177375316.6198730500000000

-----Explanation-----
You can see the points coordinates for the third sample from first two samples.

Difficulty: MEDIUM_HARD
Tags: Mathematics

Starter code:

Solutions:
t = int(input())
for i in range(t):
	(x, k) = map(int, input().split())
	(a1, b1) = (2, 1)
	while a1 <= k:
		(a1, b1) = (a1 * 2, a1)
	print(x / a1 * (1 + 2 * (k - b1)))


T = int(input())
for _ in range(T):
	(X, K) = [int(x) for x in input().split()]
	(x, y) = (2, 1)
	while x <= K:
		(x, y) = (x * 2, x)
	print(X / x * (1 + 2 * (K - y)))


def nextpoweroftwo(a):
	p = 1
	while p <= a:
		p = p << 1
	return p

def solution(x, k):
	n = nextpoweroftwo(k)
	xbyn = x / n
	nbytwo = n // 2
	a = k - nbytwo
	a = 2 * a + 1
	return a * xbyn
tstr = input()
t = int(tstr)
ans = []
for i in range(t):
	xk = input().split(' ')
	x = int(xk[0])
	k = int(xk[1])
	ans.append(solution(x, k))
for i in ans:
	print('%.8f' % i)


import math
T = int(input())
for _ in range(T):
	(x, k) = map(int, input().split())
	y = int(math.log2(k))
	z = 2 ** y
	m = k - z
	print((2 * m + 1) * x / 2 ** (y + 1))


import math
from decimal import Decimal
t = int(input())
for _ in range(t):
	(x, k) = list(map(int, input().split()))
	power_0f_2 = int(math.log(k, 2))
	diff = Decimal(x) / Decimal(2 ** (power_0f_2 + 1))
	remaining_points = Decimal(k) - Decimal(2 ** power_0f_2)
	if remaining_points == 0:
		print(round(Decimal(diff), 8))
	else:
		remaining_points += 1
		a = diff
		d = 2 * Decimal(diff)
		k = remaining_points
		print(round(Decimal(a) + Decimal(k - 1) * Decimal(d), 6))


from math import log, floor
T = int(input())
for _ in range(T):
	(X, K) = [int(x) for x in input().split()]
	k = floor(log(K, 2))
	x = 2 ** k
	print(X / x * (0.5 + K - x))


t = int(input())
for i in range(t):
	(x, k) = map(int, input().split())
	(x1, y1) = (2, 1)
	while x1 <= k:
		(x1, y1) = (x1 * 2, x1)
	print(x / x1 * (1 + 2 * (k - y1)))


import math
t = int(input())
while t > 0:
	(x, y) = map(int, input().split())
	cur_den = math.ceil(math.log(y, 2))
	cur_den = 1 << cur_den
	next_den = cur_den
	cur_den = cur_den >> 1
	if y & y - 1 == 0:
		next_den = next_den << 1
		cur_den = cur_den << 1
	ans = x / next_den
	if cur_den > 0:
		ans += (y - cur_den) * x / cur_den
	print('%.6f' % ans)
	t -= 1


two = [1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 134217728, 268435456, 536870912, 1073741824, 2147483648, 4294967296, 8589934592, 17179869184, 34359738368, 68719476736, 137438953472, 274877906944, 549755813888, 1099511627776, 2199023255552, 4398046511104, 8796093022208, 17592186044416]
for __ in range(int(input())):
	(x, k) = input().split()
	x = int(x)
	k = int(k)
	for c in two:
		if c > k:
			ours = c
			break
	ans = x / ours
	if k not in two:
		print('{0:.6f}'.format(ans * ((k - ours // 2) * 2 + 1)))
	else:
		print('{0:.6f}'.format(ans))


from sys import stdin, stdout
import math
from collections import Counter
import functools
import time

def tr():
	return range(int(line()))

def sm():
	return map(int, line().split())

def ln():
	return list(sm())

def nl():
	return int(line())

def ssm():
	return map(str, line().split())

def line():
	return stdin.readline().rstrip()

def b(x):
	return bin(x).replace('0b', '')

def o(x):
	if type(x) != type(''):
		x = str(x)
	stdout.write(x + '\n')

def osp(x):
	if type(x) != type(''):
		x = str(x)
	stdout.write(x + ' ')

def ol(x):
	stdout.write(' '.join(map(str, x)) + '\n')

def main():
	for _ in tr():
		(x, k) = sm()
		part = 2 ** math.floor(math.log2(k))
		print(x / part * (0.5 + k - part))
main()


t = int(input())
from math import log, ceil, floor
while t:
	t -= 1
	(n, k) = map(int, input().split())
	v = floor(log(k, 2))
	block = 1 << v + 1
	print(n / block * (1 + (k - 2 ** v) * 2))


import sys
T = input()
for inp in sys.stdin:
	(x, k) = map(int, inp.split())
	v = 2
	val = 1
	while val <= k:
		val *= v
	val /= 2
	ans = x / (val * 2)
	ans = ans + ans * 2 * (k - val)
	print('%.8f' % ans)


import math
t = int(input())
for i in range(0, t):
	line = input()
	l = line.split(' ')
	x = int(l[0])
	k = int(l[1])
	q = 0
	a = 0
	b = x
	p = 0
	lg = math.floor(math.log(k, 2))
	pw = math.pow(2, lg + 1)
	temp = x / pw
	a = temp
	p = a
	tw = math.pow(2, lg)
	temp = x / tw
	q = int(tw)
	p = a + (k - q) * 2 * a
	print('%.10f' % p)


import math
for _ in range(int(input())):
	(x, k) = map(int, input().split())
	a = math.floor(math.log2(k))
	b = k - math.pow(2, a)
	c = x / math.pow(2, a + 1) * (2 * b + 1)
	print(round(c, 10))


def solve():
	[x, k] = input().split()
	(x, k) = (float(x), int(k))
	cnt = 1
	while cnt < k:
		(k, cnt) = (k - cnt, cnt * 2)
	print('%.6f' % (x / (cnt * 2) + (k - 1) * x / cnt))
for t in range(0, int(input())):
	solve()


import math
t = int(input())
while t:
	(x, k) = map(int, str(input()).split())
	if k == 1:
		ans = float(x / 2.0)
		print('%.12f' % ans)
	else:
		l = int(math.log(k, 2))
		pre = int(1 << l)
		l += 1
		nex = int(1 << l)
		d1 = float(x / pre)
		d2 = float(x / nex)
		if not k & k - 1:
			print('%.12f' % d2)
		else:
			dist = int(k - pre)
			ans = float(d2 + dist * d1)
			print('%.12f' % ans)
	t -= 1


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	b = len(str(bin(k))) - 3
	dd = 2 ** b
	print((k - dd) * (n / dd) + n / (2 * dd))


from math import log2, floor

def soln(x, k):
	n = k - (1 << floor(log2(k)))
	return (2 * n + 1) * x / (1 << floor(log2(k)) + 1)
for _ in range(int(input())):
	(x, k) = map(int, input().split())
	print(soln(x, k))


from math import *
for _ in range(int(input())):
	(x, k) = input().split()
	(x, k) = (int(x), int(k))
	temp = int(log2(k)) + 1
	ans = k % pow(2, temp - 1) * (x / pow(2, temp - 1)) + x / pow(2, temp)
	print(ans)


a = int(input())
from bisect import bisect_right as br
b = [1]
for i in range(41):
	b.append(b[-1] * 2)
for _ in range(a):
	aa = list(map(int, input().rstrip().split()))
	c = br(b, aa[1])
	if b[c] == b[c - 1]:
		print(aa[0] / b[c])
	else:
		print(aa[0] / b[c] + aa[1] % b[c - 1] * (aa[0] / b[c - 1]))


from math import *

def pow2le(n):
	e = floor(log(n, 2))
	return 2 ** (e + 1)

def main():
	T = eval(input())
	for t in range(T):
		(x, k) = [int(z) for z in input().split()]
		den = pow2le(k)
		b = den // 2
		diff = k - b
		num = (1 + 2 * diff) * x
		print('%.6f' % (num / den))
main()


import math
t = int(input())
for i in range(t):
	(x, k) = map(int, input().split())
	y = int(math.log2(k))
	z = 2 ** y
	m = k - z
	ans = (2 * m + 1) * x / 2 ** (y + 1)
	print(ans)