4151. 忠实粉丝

【题目背景】

某高中正在进行校园歌手大赛，Alice 与 Bob 为了争抢粉丝大打出手。

【题目描述】

Catherine 为了平息 Alice 和 Bob 的战斗，找出了他们两个的支持者，并让他们站在操场上。

我们认为操场是一个 $n\times m$ 的网格，而如果对于任意一个 $2\times 2$ 的网格，里面有超过 $1$ 个 Alice 的支持者，操场就会发生混战。但是 Catherine 发现，存在一种合适的安排方法，使得操场不会发生混战。

现在 Alice 为了知道自己的胜算，向你询问她的支持者至多有多少个？

【输入格式】

第一行，数据组数 $T$。

对于每组数据，输入格式如下：

一行两个正整数 $n,m$。

【输出格式】

对于每组数据，输出格式如下：

一行一个整数表示答案。

【样例1输入】

3
2 2
2 3
3 4

【样例1输出】

1
2
4

【样例1说明】

对于 $3\times 4$ 的操场，可以采用如下方式放置：

ABBA
BBBB
ABBA

【样例2】

样例2下载

【数据规模与约定】

特殊性质：$n<m$。

对于 $100\%$ 的数据，$1\le T\le 10^3,1\le n,m\le 10^9$。

【来源】

校际联合邀请赛第6场语法组T2