题目描述

大户爱有一个长度为 $N$ 的正整数数组 $a$，初始你不知道每个位置的数字具体是多少，但你得到了 $M$ 个提示，每个提示形如 x y g，表示 $a_x$ 和 $a_y$ 的最大公因数为 $g$。然后你要回答 $Q$ 个问题，每个问题形如 x y，你需要回答 $a_x$ 和 $a_y$ 的最大公因数最小可能是多少。 数据范围：$g\leq 30,N,M,Q \leq 2\times 10^5$。题目保证提示是不矛盾的。

输入格式

第一行一个数字 $T$，表示数据组数（$T \leq 5$）。对于每组数据： 第一行三个整数 $N,M,Q$。 接下来 $M$ 行每行三个整数 $x,y,g$，表示 $a_x$ 和 $a_y$ 的最大公因数为 $g$。 接下来 $Q$ 行每行两个整数 $x,y$，表示询问 $a_x$ 和 $a_y$ 的最大公因数最小可能是多少。

输出格式

对于每组数据，输出 $Q$ 行，每行一个整数，表示对应问题的答案。

1
6 6 5
1 2 4 
2 3 8
3 4 1
4 5 3
5 6 3
1 5 2
1 3
1 4
4 6
2 5
1 6

4
1
3
2
1