human
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] 
mod =
=====
What is a Python program 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 program 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.
 1000000007
from math import factorial, ceil, pow, sqrt, floor
from sys import stdin, stdout
from collections import defaultdict, Counter, deque
#from bisect import bisect_left, bisect_right
# import sympy
# from itertools import permutations
# import numpy as np
 
#           n = int(stdin.readline())
#           stdout.write(str())
#           s = stdin.readline().strip('\n')
#           n,k=map(int, stdin.readline().split())
#           li = list(map(int, stdin.readline().split()))
# def SieveOfEratosthenes(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
#     return prime
# def isprime(n):
#     if n==1:
#         return False
#     for i in range(2,int(sqrt(n))+1):
#         if n%i==0:
#             return False
#     return True
# def issqrt(n):
#     p=int(sqrt(n))
#     if p*p==n:
#         return True
#     else:
#         return False
# prime=SieveOfEratosthenes(10**5)
# prime[1]=False
for _ in range(int(stdin.readline())):
    n,s=map(int, stdin.readline().split())
    if n==1:
        print(s)
    else:
        # if s>=n:
        r=n-((n-1)//2)
        print(s//r)
        # else:
        #     x=n-s
        #     if x<n//2:
        #         print(1)
        #     else:
        #         print(0)