公约数

题目背景

在收卷最后五分钟,pg发现了卷子反面还有一道大题。 题解:https://blog.csdn.net/kkkksc03/article/details/85008136

题目描述

求 [![](https://cdn.luogu.com.cn/upload/pic/33775.png)](https://www.luogu.org/paste/zltm8ddt) 由于答案可能过大,输出答案对$10^9+7$取模的值。

输入输出格式

输入格式


第一行一个正整数$T$,为数据组数。 下面$T$行,每行$3$个整数,为$n,m,p$。

输出格式


共$T$行,每行一个整数,为答案。

输入输出样例

输入样例 #1

2
10 12 11
30 20 25

输出样例 #1

25302
573830

说明

前$10\%$的数据,$T=5~,~40 \le n,m,p \le 100.$ 对于另外$20\%$的数据,$T=50~,~100 \le n,m,p \le 5\times 10^4.$ 对于另外$20\%$的数据,$T= 20~,~4\times 10^6 \le n,m,p \le 5\times 10^6$ 对于另外$50\%$的数据,$T=10^3~,~10^7 \le n,m,p \le 2\times 10^7$