Problem Description

One day, Master oy created a new function to celebrate his becoming a 'huntian' in majsoul.

$f(n,a,b)=\sum_{i=1}^n \sum_{j=1}^i gcd(i^a-j^a,i^b-j^b)[gcd(i,j)=1]\%(10^9+7)$

Given n, a and b, Master oy wanted Newbie jj who was still a 'chuxin' to answer the value of $f(n,a,b)$.

Input

There are multiple test cases.

The first line contains an integer T, indicating the number of test cases.

For each test case, there are three positive integers n, a and b which are separated by spaces. It's guaranteed that $a$ and $b$ are coprime.

$1 \le n,a,b \le 10^9$

$T=10^4$, but there are only 10 test cases that n is over $10^6$.

Output

For each test case, an integer in one line representing your answer.

2
1 2 3
100 2 3

0
101542