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.util.*;


import java.io.*;
public class Main {
		static long mod = 1000000007;
		static PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
		public static void main(String[] args) throws IOException  {
			FastReader sc = new FastReader();
			int t  = sc.nextInt();
			while( t-- > 0) {
				int n = sc.nextInt();
				int mid = (n+1)/2;
				mid = n - mid;
				long sum = sc.nextLong();
				// (x+1)(n-mid) + x = sum
				out.println((sum)/(mid+1));
			}
			out.flush();
		}		

		public static int[] nextLargerElement(int[] arr, int n)	{ 
			Stack<Integer> stack = new Stack<>();
			int rtrn[] = new int[n];
	        rtrn[n-1] = -1;
	        stack.push( n-1);
	        for( int i = n-2 ;i >= 0 ; i--){
	            int temp = arr[i];
	            int lol = -1;
	            while( !stack.isEmpty() && arr[stack.peek()] <= temp){
	            	if(arr[stack.peek()] == temp ) {
	            		lol = stack.peek();
	            	}
	                stack.pop();
	            }
	            if( stack.isEmpty()){
	            	if( lol != -1) {
	            		rtrn[i] = lol;
	            		}
	            	else {
	                rtrn[i] = -1;
	            	}
	            }
	            else{
	            	rtrn[i] = stack.peek();
	            }
	            stack.push( i);
	        }
	        return rtrn;
		}
		
		 static int gcd(int a, int b)
		    {
		        if (a == 0)
		            return b;
		        return gcd(b % a, a);
		    }
		     
//		    // method to return LCM of two numbers
//		    static int lcm(int a, int b)
//		    {
//		        return (a / gcd(a, b)) * b;
//		    }
	 
		static HashMap<Long,Long> primefactor( long n){
			HashMap<Long ,Long> hm = new HashMap<>();
			long temp = 0;
			while( n%2 == 0) {
				temp++;
				n/=2;
	 		 }	
			if( temp!= 0) {
	 			 hm.put( 2L, temp);
	 		 }
	 		 long c = (long)Math.sqrt(n);
	 		 for( long i = 3 ; i <= c ; i+=2) {
	 			 temp = 0;
	 			 while( n% i == 0) {
	 				 temp++;
	 				 n/=i;
	 			 }
	 			 if( temp!= 0) {
	 				 hm.put( i, temp);
	 			 }
	 		 }
	 		 if( n!= 1) {
	 			 hm.put( n , 1L);
	 		 }
	 		 return hm;
	 		// this is the link where i found this method
	 		 // https://www.geeksforgeeks.org/print-all-prime-factors-of-a-given-number/
	 	 }
	 
		 static class FastReader {
		        BufferedReader br;
		        StringTokenizer st;
		 
		        public FastReader()
		        {
		            br = new BufferedReader(
		                new InputStreamReader(System.in));
		        }
		        
		        String next()
		        {
		            while (st == null || !st.hasMoreElements()) {
		                try {
		                    st = new StringTokenizer(br.readLine());
		                }
		                catch (IOException e) {
		                    e.printStackTrace();
		                }
		            }
		            return st.nextToken();
		        }
		 
		        int nextInt() { return Integer.parseInt(next()); }
		 
		        long nextLong() { return Long.parseLong(next()); }
		 
		        double nextDouble()
		        {
		            return Double.parseDouble(next());
		        }
		 
		        String nextLine()
		        {
		            String str = "";
		            try {
		                str = br.readLine();
		            }
		            catch (IOException e) {
		                e.printStackTrace();
		            }
		            return str;
		        }
		    }
		
}