You are given two positive integers n and s. Find the maximum possible median of an array of n non-negative integers (not necessarily distinct), such that the sum of its elements is equal to s.

A median of an array of integers of length m is the number standing on the ⌈ {m/2} ⌉-th (rounding up) position in the non-decreasing ordering of its elements. Positions are numbered starting from 1. For example, a median of the array [20,40,20,50,50,30] is the ⌈ m/2 ⌉-th element of [20,20,30,40,50,50], so it is 30. There exist other definitions of the median, but in this problem we use the described definition.

Input

The input consists of multiple test cases. The first line contains a single integer t (1 ≤ t ≤ 10^4) — the number of test cases. Description of the test cases follows.

Each test case contains a single line with two integers n and s (1 ≤ n, s ≤ 10^9) — the length of the array and the required sum of the elements.

Output

For each test case print a single integer — the maximum possible median.

Example

Input


8
1 5
2 5
3 5
2 1
7 17
4 14
1 1000000000
1000000000 1


Output


5
2
2
0
4
4
1000000000
0

Note

Possible arrays for the first three test cases (in each array the median is underlined):

  * In the first test case [\underline{5}] 
  * In the second test case [\underline{2}, 3] 
  * In the third test case [1, \underline{2}, 2] 
# template begins
#####################################
 
# import libraries for input/ output handling
# on generic level
import atexit, io, sys, math, heapq

#input handling
#input of single integer
def get_int(): return int(sys.stdin.readline().strip())
#input of multiple integers
def get_ints(): return map(int, sys.stdin.readline().strip().split())
#input of list
def get_list(): return list(map(int, sys.stdin.readline().strip().split()))
#input of string
def get_string(): return sys.stdin.readline().strip()

#output handling
#writing int output
def write_int(a): sys.stdout.write(str(a)+"\n")
#writing String
def write_str(a): sys.stdout.write(a+"\n")
#writing Array
def write_list(arr): sys.stdout.write(" ".join(map(str, arr)) + "\n")

#general functions
#swap
def swap(arr, a, b):
    arr[a]^=arr[b]
    arr[b]^=arr[a]
    arr[a]^=arr[b]

#NumberOfDigits
def int_len(a): return math.floor(math.log(a,10))+1

#Powerof2
def isPowerOfTwo(x): return x and (not(x & (x-1)))

#Sieve
def Sieve(n):
    prime = [True for i in range(n+1)]
    p = 2
    while (p * p <= n):
        if (prime[p] == True):
            for i in range(p * p, n+1, p):
                prime[i] = False
        p += 1
    res = []
    for i in range(2,len(prime)):
        if (prime[i]):
            res.append(i)
    return res

#binarySearch
def binarySearch (arr, l, r, x):
    if r >= l:
  
        mid = l + (r - l) // 2
        if arr[mid] == x:
            return mid
        elif arr[mid] > x:
            return binarySearch(arr, l, mid-1, x)
        else:
            return binarySearch(arr, mid + 1, r, x)
    else:
        return -1
def search(arr,x): return binarySearch(arr,0,len(arr)-1,x)

#Array to String
def toString(A): return''.join(A)

# String to array
def toArray(str): return str.split()

#ArraySum
def arrSum(Arr):
    Sum =0
    for i in range (len(Arr)):
        Sum+=Arr[i]
    return Sum

def computeXOR(n) :
 
    # Modulus operator are expensive
    # on most of the computers. n & 3
    # will be equivalent to n % 4.
 
    # if n is multiple of 4
    if n % 4 == 0 :
        return n
 
    # If n % 4 gives remainder 1
    if n % 4 == 1 :
        return 1
 
    # If n%4 gives remainder 2
    if n % 4 == 2 :
        return n + 1
 
    # If n%4 gives remainder 3
    return 0
 

#####################################
# template ends

# Code begins
#####################################

N = get_int()

while (N>0):
    A,B = get_ints()
    if A>B :
        print(0)
    else:
        if (A==1):
            print(B)
        elif A==2:
            print(B//2)
        else:
            P = math.ceil(A/2)
            A-=(P-1)
            print(B//A)

    N-=1
    



#####################################
# Code ends


# Creating 2D array sol = [[0 for i in range(N)] for j in range(N)]