• For Solution

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

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

Median Maximization solution codeforces

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

Each test case contains a single line with two integers nn and ss (1n,s1091≤n,s≤109) — the length of the array and the required sum of the elements.

Median Maximization solution codeforces

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

Example

input

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


Median Maximization solution codeforces

Copy
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 [5][5_]
• In the second test case [2,3][2_,3]
• In the third test case [1,2,2][1,2_,2]