胖陈低着头看了看手上的劳力士，喊了一位财务过来发工资，工资一共有n元，要发给m位员工。他命令财务发工资时要保证公平公正公开，最高与最低的工资差最多为1元，且拿到较高工资的员工不能超过总人数(不包含财务与胖陈)的一半。财务只有发出最多的工资才能避免被送去非洲。

真是朴实无华且枯燥。

第一行输入一个整数t(1<t<10^5)代表有t家公司

接下来t行，每行输入两个整数n,m(1<n,m<10^9)代表每家公司发n元工资给m人

每行输出当前公司最多发出多少元工资