Problem Description

题目描述

为了方便市民出行，缓解地面上的道路拥堵问题，S 市决定在地底下建一些地铁。

根据城市规划，S 市的地下网络将由 $n$ 条横向通道和 $m$ 条纵向通道构成。地铁站将设置在所有横向通道与纵向通道的交叉处，共 $n\times m$ 处。

地下网络的所有站点都需要被地铁线路覆盖，地铁线路之间可以有重叠部分。

每条线路上的站点必须位于同一横向或纵向通道，即线路不能拐弯。线路网必须连通，任意地铁站之间可经若干次换乘到达。

例如，当 $n=5$，$m=7$ 时，图示网络符合要求。

求覆盖所有站点且使线路网连通的最少线路数。

输入格式

第一行输入 $T$，之后每组一行两个正整数 $n,m$。

输出格式

每组数据输出最少线路数。

样例

样例 1

提示

样例解释与数据范围见题面。

3
1 1
1 2
2 2

1
1
3