SP5084 GCD3 - Discrete Math Problem

给定 $N,M,K (1 \le N, M \le 10^{400}, 1 \le K\le 16)$，其中 $N,M$ 满足存在互质的正整数 $a,b$，使得 - $N = a + b$ - $M = a^2 + b^2 - (2^K - 2) \times a \times b$ 求 $N,M$ 的最大公约数。

本题多组数据。 第一行一个整数 $T(1 \le T \le 10000)$，表示有 $T$ 组数据。 之后 $T$ 行，每行有三个数 $N,M,K$。

输出 $T$ 行，第 $i$ 行表示第 $i$ 组测试数据的 $(N, M)$ 的最大公约数。

翻译提供者：[Genshin_ht](https://www.luogu.com.cn/user/1646296)。