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 Test {
	public static void main(String[] args) throws IOException, InterruptedException {
	   Scanner sc = new Scanner(System.in);
	   PrintWriter pw = new PrintWriter(System.out);
      int t = sc.nextInt();
      while(t-->0) {
       int n = sc.nextInt();
       int s = sc.nextInt();
        int mid = (n/2)+1;
        
     // System.out.println(mid);
        
        	System.out.println((s/mid));
        
       
       
       
       
	}}
	static long minCost;
	static long T;
	static long V;
	static long currVolume;
	static long currCost;
	static long []flowRate;
	static long [] cost;
	static int []dur;
    static int m;
    static int currRem;
	static LinkedList<Integer> currsol ;
	static LinkedList<Integer> sol;
	static void solve (int i) {
	      if(i ==n) {
	    	 // System.out.println(currVolume);
	    	  if(currVolume>=V) {
	    		  if(currCost < minCost) {
	    			  minCost = currCost;
	    		  }
	    	  }
	    	  return;
	      }
	      // open 
	      currVolume += flowRate[i]*T;
	      currCost += cost[i];
	      solve(i+1);
	      
	      currVolume -= flowRate[i]*T;
	      currCost -= cost[i];
	      solve(i+1);
	    
	}
	static int bitCount (int msk) {
		int comp = 1;
		int count = 0;
		while(comp<=msk) {
			if((msk&comp)!=0) {
				count++;
			}
			comp = comp<<1;
		}
		return count;
	}
	static long [] sat;
	static char[] s;
	static char[] t;
	static int k;
	static int [][] map;
	static long [] value;
 
static ArrayList<String> ans ;	
static int w;
 
    static int n;
	static long [][]   dp;
	static ArrayList<Pair> items;
	static int d1;
		   static class triple {
	            int u;
	            int v;
	            int z;
	 
	            public triple(int u, int v, int z) {
	                this.u = u;
	                this.v = v;
	                this.z = z;
	            }
	 
	            public String toString() {
	                return "triple{" +
	                        "u=" + u +
	                        ", v=" + v +
	                        ", z=" + z +
	                        '}';
	            }
	 
	            public boolean equals(Object o) {
	                if (this == o) return true;
	                if (o == null || getClass() != o.getClass()) return false;
	                triple triple = (triple) o;
	                return u == triple.u &&
	                        v == triple.v &&
	                        z == triple.z;
	            }
	 
	            public int hashCode() {
	                return Objects.hash(u, v, z);
	            }}
	 
 
			
 
 
 
	static class Pair implements Comparable {
		long x;
		long y;
		public Pair (long x, long y) {
			this.x = x;
			this.y = y;
			
		}
		public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Pair triple = (Pair) o;
            return x == triple.x &&
                    y == triple.y ;
        }
		@Override
		public int compareTo(Object arg0) {
			Pair p = (Pair) arg0;
			if(Long.compare(x, p.x)==0) {
				return Long.compare(y, p.y);
			}
			return Long.compare(x, p.x);
		}
	}static long modPow(long a, long x, long p) {
	    //calculates a^x mod p in logarithmic time.
	    long res = 1;
	    while(x > 0) {
	        if( x % 2 != 0) {
	            res = (res * a) % p;
	        }
	        a = (a * a) % p;
	        x /= 2;
	    }
	    return res;
	}
 
	static long modInverse(long a, long p) {
	    //calculates the modular multiplicative of a mod m.
	    //(assuming p is prime).
	    return modPow(a, p-2, p);
	}
	static long [] fact;
	static long nCr1(int n, int r,long mod)
	{ //System.out.println(r);
	   long numerator = fact[n]%mod;
	  // System.out.println(r+" "+(n-r));
	   long deno = ((fact[r]%mod)*(fact[n-r]%mod))%mod;
	
	    return (numerator*modInverse(deno,mod))%mod;
	}
 
	static ArrayList <Integer> prime;
	 static void simpleSieve(int limit)
	    {   
	        // Create a boolean array "mark[0..n-1]" and initialize
	        // all entries of it as true. A value in mark[p] will
	        // finally be false if 'p' is Not a prime, else true.
	        boolean mark[] = new boolean[limit+1];
	         
	        for (int i = 0; i < mark.length; i++)
	            mark[i] = true;
	      
	        for (int p=2; p*p<limit; p++)
	        {
	            // If p is not changed, then it is a prime
	            if (mark[p] == true)
	            {
	                // Update all multiples of p
	                for (int i=p*p; i<limit; i+=p)
	                    mark[i] = false;
	            }
	        }
	      
	        // Print all prime numbers and store them in prime
	        for (int p=2; p<limit; p++)
	        {
	            if (mark[p] == true)
	            {
	                prime.add(p);
	               // System.out.print(p + "  ");
	            }
	        }
	    }
 
	 
	 public static long gcd (long a, long b ) {
		 if(b==0) {
			 return a;
		 }
		 else {
			 return gcd (b, a%b);
		 }
	 }
	 
 static class Scanner {
 		StringTokenizer st;
 		BufferedReader br;
  
 		public Scanner(InputStream s) {
 			br = new BufferedReader(new InputStreamReader(s));
 		}
        public Scanner(FileReader r) {
        	br = new BufferedReader(r);
        }
 		public boolean hasNext() {
 			// TODO Auto-generated method stub
 			return false;
 		}
  
 		public String next() throws IOException {
 			while (st == null || !st.hasMoreTokens())
 				st = new StringTokenizer(br.readLine());
 			return st.nextToken();
 		}
  
 		public int nextInt() throws IOException {
 			return Integer.parseInt(next());
 		}
  
 		public long nextLong() throws IOException {
 			return Long.parseLong(next());
 		}
  
 		public String nextLine() throws IOException {
 			return br.readLine();
 		}
  
 		public double nextDouble() throws IOException {
 			String x = next();
 			StringBuilder sb = new StringBuilder("0");
 			double res = 0, f = 1;
 			boolean dec = false, neg = false;
 			int start = 0;
 			if (x.charAt(0) == '-') {
 				neg = true;
 				start++;
 			}
 			for (int i = start; i < x.length(); i++)
 				if (x.charAt(i) == '.') {
 					res = Long.parseLong(sb.toString());
 					sb = new StringBuilder("0");
 					dec = true;
 				} else {
 					sb.append(x.charAt(i));
 					if (dec)
 						f *= 10;
 				}
 			res += Long.parseLong(sb.toString()) / f;
 			return res * (neg ? -1 : 1);
 		}
  
 		public boolean ready() throws IOException {
 			return br.ready();
 		}
  
 	}
}