Description

定义由长度为 $n$ 的非负整数数列的中位数为这个数列从小到大排序后位于第 $[n/2]$ 位的数，例如 $[20,40,20,50,50,30]$ 的中位数是 $30$ 。但是求一个非负整数数列的中位数这道题太简单了，所以[丛雨]把这个问题改成了给定 $n$ 和 $s$ ，最大化长度为 $n$ 且和为 $s$ 的非负整数数列的中位数。丛雨发现自己并不会做这个题，所以决定来考考你。

Format

Input

每个输入文件包含多组数据。

第一行一个整数 $T$ , 表示数据的组数。

接下来 $T$ 行，每行包含两个整数 $n, s$ ，$n$ 为数列长度， $s$ 为数列元素之和。

Output

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

Samples

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

Limitation

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

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

对于 $100\%$ 的数据，保证 $1 \le T \le 10^5, 1 \le n, s \le 10^9$ 。

1s, 128MB for each test case.