题目描述

长度为 $n$，公差为 $k$，首项为 $x$ 的等差数列是 $x,x+k,x+2k,\ldots,x+(n-1)k$ 的数列。

长度为 $n$，公比为 $k$，首项为 $x$ 的等比数列是 $x,kx,k^2x,\ldots,k^{n-1}x$ 的数列。

现在给你一个等差或等比数列，求出其中 $n$ 个数的最大公约数。

输入格式

本题有多组测试数据，第一行输入测试数据组数 $T$。

接下来 $T$ 行，每行 $4$ 个整数 $op,n,k,x$，$op=0$ 表示所求数列是等差数列，$op=1$ 表示所求数列是等比数列，$n,k,x$ 的含义见题目描述。

输出格式

对于每组数据，输出一行，表示等差或等比数列中 $n$ 个数的最大公约数。

2
0 4 4 6
1 3 3 5

2
5

提示

样例解释

对于第一组测试数据，该数列为 $6,10,14,18$，最大公约数为 $\gcd(6,10,14,18)=2$。

对于第二组测试数据，该数列为 $5,15,45$，最大公约数为 $\gcd(5,15,45)=5$。

数据范围

对于 $100\%$ 的数据，$1\le T\le 10$，$0\le op\le1$，$1 \le n,k,x \le {10}^{18}$。