题目描述

给定直角坐标系中两个点 $A$ 和 $B$ 的坐标 $(a_x, a_y)$、$(b_x, b_y)$，其中 $a_x, a_y, b_x, b_y$ 均为整数。求线段 $AB$ 上 $A$ 和 $B$ 之间的格点个数（不包括 $A$ 和 $B$ 本身）。

本题需要处理多个测试数据。

输入格式

第一行一个整数 $T$，表示测试数据组数（$1 \le T \le 100$）。

接下来 $T$ 行，每行四个整数 $a_x \; a_y \; b_x \; b_y$（$-10^9 \le a_x, a_y, b_x, b_y \le 10^9$）。

输出格式

对每组测试数据，输出一行，表示对应的格点个数。

样例

1
1 2 25 20

5

说明/提示

记 $x$ 坐标差的绝对值为 $xx$，$y$ 坐标差的绝对值为 $yy$。若 $A=B$，答案为 $0$。否则计算 $g = \gcd(xx, yy)$（若 $xx$ 或 $yy$ 为 $0$，则 $g$ 取非零的那个值），答案为 $g-1$。