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 = 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)