题目描述

大户爱有一个长度为 \(N\) 的正整数数组 \(a\)，初始你不知道每个位置的数字具体是多少，但你得到了 \(M\) 个提示，每个提示形如 x y g，表示 \(a_x\) 和 \(a_y\) 的最大公因数为 \(g\)。然后你要回答 \(Q\) 个问题，每个问题形如 x y，你需要回答 \(a_x\) 和 \(a_y\) 的最大公因数最小可能是多少。 数据范围： \(g \le 30\)，\(N,M,Q \le 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