human
PYTHON3 solution for "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] ":


 ... What is a Python code to 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?
assistant
#Here is Python code to 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.
 import os,sys
from io import BytesIO, IOBase

from collections import deque, Counter,defaultdict as dft
from heapq import heappop ,heappush
from math import log,sqrt,factorial,cos,tan,sin,radians,log2,ceil,floor,gcd
from bisect import bisect,bisect_left,bisect_right
from decimal import *
import sys,threading
from itertools import permutations, combinations
from copy import deepcopy
input = sys.stdin.readline

def modI(a, m):

    m0=m
    y=0
    x=1;
    if(m==1): return 0;
    while(a>1):
    
        q=a//m;
        t=m;
        m=a%m;
        a=t;
        t=y;
        y=x-q*y;
        x=t;
    
    if(x<0):x+=m0;
    return x;

ii = lambda: int(input())
si = lambda: input().rstrip()
mp = lambda: map(int, input().split())
ms=  lambda: map(str,input().strip().split(" "))
ml = lambda: list(mp())
mf = lambda: map(float, input().split())

alphs = "abcdefghijklmnopqrstuvwxyz"

# stuff you should look for
	#  int overflow, array bounds
	#  special cases (n=1?)
	#  do smth instead of nothing and stay organized
	#  WRITE STUFF DOWN
	#  DON'T GET STUCK ON ONE APPROACH

#

def solve():
    
    n,s=mp()
    idx=ceil(n/2)
    idx-=1
    
    temp=s//(n-idx)
    print(temp)
    

 
BUFSIZE = 8192
 
 
class FastIO(IOBase):
    newlines = 0
 
    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None
 
    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()
 
    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr =...