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] 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

	public class practice{
		public static void main(String[] args){
			FastScanner r = new FastScanner();					
			int t = r.i() ,n,s;
			StringBuffer ans = new StringBuffer("");
			while(t-->0) {
				n = r.i();
				s = r.i();

				if(n%2==0)
				n -= (n/2 - 1);
				else
					n -= (n/2 );
				
//				p(s/n);
				ans.append(s/n + "\n");
				
			}				
			p(ans);
		}

		
		static <T> void p(T s) {
			System.out.println(s);
		}
		
		static void p() {
			System.out.println();
		}		
		static <T> void pn(T s) {
			System.out.print(s);
		}

	}
		

	
	class FastScanner {
	    BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
	    StringTokenizer st=new StringTokenizer("");
	    String n() {
	        while (!st.hasMoreTokens())
	            try {
	                st=new StringTokenizer(br.readLine());
	            } catch (IOException e) {
	                e.printStackTrace();
	            }
	        return st.nextToken();
	    }
	    int[] ia(int n) {
	    	int[] arr = new int[n];
	    	for(int i=0;i<n;i++)
	    		arr[i] = i();
	    	return arr;
	    }
	    String[] sa(int n) {
	    	String[] arr = new String[n];
	    	for(int i=0;i<n;i++)
	    		arr[i] = n();
	    	return arr;
	    }
	    long[] la(int n) {
	    	long[] arr = new long[n];
	    	for(int i=0;i<n;i++)
	    		arr[i] = l();
	    	return arr;
	    }
	    String nl()
	    {
	        String str = "";
	        try
	        {
	            str = br.readLine();
	        }
	        catch (IOException e)
	        {
	            e.printStackTrace();
	        }
	        return str;
	    }

	    int i() {
	        return Integer.parseInt(n());
	    }
	    long l() {
	        return Long.parseLong(n());
	    }
	}
