俊俊和鹏鹏期待着在大学开始新的一年。当他们进入新教室时，他们观察了学生被安排在n*m网格中。r行和c列中的座位用（r，c）表示，两个座位（a，b）和（c，d）之间的距离表示为|a-c|+|b-d|

作为班长，鹏鹏可以获得整整k桶粉色油漆：

•首先，鹏鹏在教室里选择k个座位刷上粉色油漆。一桶油漆正好可以刷一个座位。

•在鹏鹏用粉刷过k个座位后，俊俊会选择他坐在哪里。由于他不喜欢粉红色，所以他不会选择涂成粉红色的座位。

•在俊俊选择座位后，鹏鹏为自己选择了一个座位。她可以选择任何座位，无论是否油漆，除了一个由俊俊选择的座位。

俊俊想选择一个尽可能靠近鹏鹏的座位。然而，鹏鹏想坐得离俊俊尽可能远。

现在，俊俊想知道，如果鹏鹏有k（k=0,1，…，n*m−1）桶油漆，如果俊俊和鹏鹏都知道对方的意图，并且都尽可能从战略上行动，那么俊俊能和鹏鹏坐得多近？请帮助满足俊俊的好奇心！

输入由多个测试用例组成。第一行包含一个整数t(1≤t≤50000)-测试用例的数量。

每个测试用例的第一行包含两个整数n，m（2≤n*m≤10^5)-教室座位的行数和列数。 

对于样例1，鹏鹏具有k=3个粉色油漆，一个可能的选择序列如下：在位置（1,2） ，（2,2），（3,2）处对座椅进行喷漆涂有粉红色油漆。俊俊在（3,1）处选择座位，鹏鹏在（1,3）处选择座位。 因此，鹏鹏和俊俊之间的距离为| 3−1|+|1−3|=4 ，我们可以证明这确实是给定约束下的最小可能距离。可能还有其他的座位选择也会得到相同的答案。

对于k=0，俊俊可以决定坐在（2,2），鹏鹏可以决定坐在（4,3），因此他们之间的距离为| 2−4|+|2−3|=3 

上述两种情况，如下图所示

何俊鹏2021