#y1020. 打台球2

打台球2

Description

对于一个横向长为 nn,纵向长为 mm 的台球桌。

从左下角向右 xx 个单位长度的位置发球,角度为 4545 度,假设球的动力无限,直到进洞才停止(台球桌的四个角都有洞)。

设左上方的洞为 11,左下方的洞为 33,右上方的洞为 22,右下方的洞为 44。

求最后球会进哪个编号的洞。

Format

Input

第一行一个数字 TT。

接下来 TT 行,每行两个正整数 n,m,xn,m,x。

Output

一行一个整数,即答案。

Samples

2
3 2 2
3 2 0

3
1

Limitation

对于第一组数据,设左下角坐标为 (0,0)(0,0)。

路线为:(2,0)→(3,1)→(2,2)→(0,0)(2,0)\to(3,1)\to(2,2)\to(0,0)

T⩽105T\leqslant10^5

1≤m,x<n≤2×1091\le m,x\lt n\le2 \times 10^9

保证 nn 是质数。

相关

在下列比赛中:

ACM