[ICPC2020 Shanghai R] Traveling in the Grid World


### 题目描述 考虑具有 $n$ 行和 $m$ 列的网格模式。总共有$(n+1)\times(m+1)$网格点,即$n+1$水平线和$m+1$垂直线的交点。我们将水平线从上到下从 $0$ 到 $n$ 编号。我们将垂直线从左到右编号从 $0$ 到 $m$。水平线 $i$ 和垂直线 $j$ 的交点命名为 $(i,j)$($0 \le i \le n, 0 \le j \le m$)。 当您在网格世界中旅行时,会有一些限制。当您位于点 $(x,y)$ 时,您可以选择一个目的地 $(x',y')$ 并沿着 $(x,y)$ 和 $(x',y')$ 之间的线段步行到该目的地。我们将此操作称为 $\textit{walk}$。如果它们之间的线段上存在另一个不同于 $(x,y)$ 和 $(x', y')$ 的网格点,则禁止行走。您可以随心所欲地走很多次,但连续两次步行的方向不能相同。(具体来说,如果从 $(x_0,y_0)$ 到 $(x_1, y_1)$,然后从 $(x_1, y_1)$ 到 $(x_2, y_2)$,则必须确保 $(x_0-x_1)(y_1-y_2) \neq (x_1-x_2)(y_0-y_1)$。从 $(x,y)$ 到 $(x',y')$ 的步行长度定义为两个端点之间的欧几里得距离 $\sqrt{(x-x')^2+(y'-y)^2}$。 从 $(0,0)$ 开始,您计划通过几次步行到达 $(n,m)$。由于烦人的规则,您可能需要一些转折点来实现您的目标。请找到您步行的最小总长度。 ### 输入格式 有多个测试用例。输入的第一行包含一个整数 $T$,表示测试用例的数量。对于每个测试用例, 第一行包含两个整数 $n,m$ ($1 \le n,m \le 10^6$),表示网格图的大小。 保证所有测试用例中 $\max(n,m)$ 的值之和不超过 $10^6$。


Consider a grid pattern with $n$ rows and $m$ columns. There are $(n+1)\times(m+1)$ grid points in total which is the intersections of $n+1$ horizontal lines and $m+1$ vertical lines. We number the horizontal lines from $0$ to $n$ from top to bottom. We number the vertical lines from $0$ to $m$ from left to right. The intersection of horizontal line $i$ and vertical line $j$ is named $(i, j)$ ($0\le i\le n, 0\le j\le m$). There are some constraints when you travel in the grid world. When you are located at point $(x,y)$, you can choose a destination $(x',y')$ and walk to it along the line segment between $(x, y)$ and $(x', y')$. We call this operation a $\textit{walk}$. A walk is forbidden if there exists another grid point different from $(x, y)$ and $(x', y')$ lying on the line segment between them. You can walk as many times as you want but the directions of two consecutive walks cannot be the same. (Specifically, if you walk from $(x_0, y_0)$ to $(x_1, y_1)$ and then walk from $(x_1, y_1)$ to $(x_2, y_2)$, you must make sure that $(x_0-x_1)(y_1-y_2)\neq (x_1-x_2)(y_0-y_1)$.) The length of a walk from $(x, y)$ to $(x', y')$ is defined as the Euclidean distance between the two endpoints, $\sqrt{(x-x')^2+(y'-y)^2}$. Starting from $(0,0)$, you are planning to arrive at $(n,m)$ by several walks. Because of the annoying rules, you may need some turning points to achieve your goal. Please find the minimum total length of your walks.



There are multiple test cases. The first line of the input contains an integer $T$, indicating the number of test cases. For each test case: The first line contains two integers $n,m$ ($1\le n,m \le 10^6$) indicating the size of the grid graph. It is guaranteed that the sum of the values of $\max(n,m)$ over all test cases does not exceed $10^6$.


For each test case, output the minimum total length of walks. Your answer will be considered correct if its absolute or relative error does not exceed $10 ^{-9}$.


输入样例 #1

2 2
2 3

输出样例 #1