题目背景

小S最近迷上了蛇形矩阵。蛇形矩阵的生成方式为：从矩阵的左上角（第 1 行第 1 列）出发，初始时向右移动一格，然后向左下移动，直到碰到边界；如果下方是在范围内未出界的格子，则向下移动一格接着往右上移动，否则向右移动一格接着往右上移动，直到到达边界；接着，如果右边的格子在范围内，往右移动一格，否则向下移动一格，接着往左下直到边界；重复上述操作直至经过矩阵中所有格子。

就像这样

将1~15放进一个\(3*5\)的蛇形矩阵就像这样

\(1\)	\(2\)	\(6\)	\(7\)	\(12\)
\(3\)	\(5\)	\(8\)	\(11\)	\(13\)
\(4\)	\(9\)	\(10\)	\(14\)	\(15\)

题目描述

不管是什么时候，她都喜欢蛇形矩阵。

现在小S有一串数列： 1234567891011121314151617... 。就是把正整数 \(1,2,3,4\),... 写成一个大数。

她把其中的前 \(n*m\) 个数字放进了 \(n*m\) 的一个蛇形矩阵（多余的就舍弃了），这样就成了蛇形数阵，下面就是 \(3*5\) 的蛇形数阵：

\(1\)	\(2\)	\(6\)	\(7\)	\(1\)
\(3\)	\(5\)	\(8\)	\(0\)	\(1\)
\(4\)	\(9\)	\(1\)	\(1\)	\(2\)

现在，他想问这个蛇形矩阵中第 \(i\) 行，第 \(j\) 列是什么数字。

输入输出格式

输入格式

本题包含多组测试数据，第一行一个数 \(T\)，表示数据总数。

每组数据共一行，4个整数，\(n\)，\(m\)，\(i\)，\(j\)，意义如题目所述。

输出格式

每个数据一行，表示这个蛇形矩阵第 \(i\) 行第 \(j\) 列的数字

样例 1

样例输入

3
3 5 2 2
100 100 88 88
123456789 123456789 7654321 1234567

Output

5
9
0

限制

时间限制1s，空间限制125MB

提示

样例说明

第 1 组数据就是题目描述中的矩阵。

---

数据范围(百分比为得分)

\(10\%\)的数据，\(1 \leq n,m \leq 10\)

\(30\%\)的数据，\(1 \leq n,m \leq 1000\)

\(60\%\)的数据，\(1 \leq n,m \leq 10^5\)

\(100\%\)的数据，\(T \leq 10, 1 \leq n,m \leq 10^9, 1 \leq i \leq n, 1 \leq j \leq m\)

另有\(2\%\)的数据，\(i=n,j=m\)

另有\(3\%\)的数据，\(n=1\)或\(m=1\)

---

提示

请换个角度看看这个矩阵。