题目背景

梦熊月赛钻石组

题目描述

定义由长度为 n 的非负整数数列的中位数为这个数列从小到大排序后位于第 ⌈ n/2 ⌉ 位的数。

例如[20,40,20,50,50,30] 的中位数是 30. 但是求一个非负整数数列的中位数这道题太简单了，所以小 L 把这个问题改成了给定 n 和 s ，最大化长度为 n 且和为s 的非负整数数列的中位数。小 L 发现自己并不会做这个题，所以决定来考考你。

数据格式

输入

每个输入文件包含多组数据。 第一行一个整数 T , 表示数据的组数。接下来 T 行，每行包含两个整数 n,s，n 为数列长度，s 为数列元素之和。

输出

输出 T 行，每行包含一个整数，表示长度为 n 且和为 s 的非负整数数列的最大中位数。

样例

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

5 
2 
2 
0 
4 
4 
1000000000 
0

限制

对于 20% 的数据，保证 T=1。

对于另外 30% 的数据，保证 T ≤ 10,n ≤ 5,s ≤ 10。

对于全部的数据，保证 1 ≤ T ≤ $10^5$,1 ≤ n, s ≤ $10^9$。