题目描述

给定四个正整数 $a, b, c, d$。计算 $gcd(a^b, c^d)$ 的值，并将其对 998244353 取模。

输入格式

第一行包含一个整数 $t$ ($1 \leq t \leq 10^5$)，表示测试用例的数量。

对于每个测试用例，输入只有一行，包含四个正整数 $a, b, c, d$ ($1 \leq a, b, c, d \leq 10^{18}$)。

输出格式

对于每个测试用例，输出一行一个整数，表示 $gcd(a^b, c^d)$ 对 998244353 取模后的结果。

5
2 3 3 2
4 2 8 1
6 2 9 1
7 1 11 1
10000000000000 1 10000000000000 1

1
8
9
1
586315999