飞飞有 $K$ 个矩阵，每次飞飞可以选择矩阵中任意的一个位置作为起点，每次可以往前走一步，或者向左/右旋转 $90^{\circ}$，但过程中不能走出这个矩阵。 现在飞飞想要知道，对于 $n \times m$ 的矩阵，从任意起点开始，走完整个矩阵所需要的**最少的旋转次数**。

第一行有一个正整数 $K$ $(1 \le K \le 50000)$，表示有 $K$ 个矩阵。 接下来 $K$ 行，每行两个正整数 $n, m$ $(1 \le n, m \le 10^6)$。

共 $K$ 行，每行一个正整数，表示走完整个矩阵所需要的**最少的旋转次数**。