GGGCCCDDD

2012년 8월 18일. 시대를 앞서가는 프로그래밍 연구소 Algospot에서는 새로운 슈퍼컴퓨터 AEX를 개발했다. Algospot의 연구원 altertain은 AEX의 성능을 알아보려고 GCD(최대공약수)의 합을 계산하는 간단한 프로그램을 작성했다.

int gcd(int a, int b) {
    return b ? gcd(b, a%b) : a;
}

sum = 0;
for (a = 1; a ≤ N; a++)
    for (b = 1; b ≤ N; b++)
        sum = sum + gcd(a, b);

"흠... 이 정도는 금방 계산하겠지...?"

슈퍼컴퓨터 AEX는 눈 깜짝할 사이에 계산을 마치고 답을 출력했다.

"음... 그럼 루프를 하나 늘려볼까...?"

sum = 0;
for (a = 1; a ≤ N; a++)
    for (b = 1; b ≤ N; b++)
        for (c = 1; c ≤ N; c++)
            sum = sum + gcd(gcd(a, b), c);

"와... 엄청 빠르다!"

AEX는 이번에도 순식간에 계산해냈다.

"뭐하고 있어?"

Algospot에 놀러 온 Afocuns의 연구원 rainpunch가 altertain에게 물었다.

"어, 왔어? 이번에 우리 연구소에서 슈퍼컴퓨터를 새로 개발했거든. 그거 테스트하고 있었어. 이 코드에 루프를 하나씩 늘려보던 중이야..."

코드를 본 rainpunch가 한마디 했다. "뭐야? 이 정도는 루프가 10개라도 금방 계산하겠다... 아니, 음... 1000개라도 금방 하겠는데?"

"뭐라고!? 그럼 루프 M개에 대해 누가 더 빨리 계산하는지 진검승부 한번 해볼까!?"

"좋아. 내가 의지의 차이를 제대로 보여주지."

"흥! 컴퓨터의 천재, 박수를 드려요!"

rainpunch가 떠올린 방법은 무엇일까? 우리도 좋은 방법을 한번 찾아보자.

입력은 T개의 테스트 케이스로 구성된다. 입력의 첫 줄에는 T가 주어진다.

각 테스트 케이스마다 한 줄에 정수 N과 M (2 ≤ N, M ≤ 1000)이 공백으로 구분되어 주어진다.

각 테스트 케이스마다 한 줄에 답을 하나씩 출력한다. 답이 매우 클 수 있으므로, 답을 $1\,000\,000\,007$로 나눈 나머지를 출력한다.

N = 10, M = 4인 경우 아래처럼 계산할 수 있다.

sum = 0;
for (a = 1; a ≤ 10; a++)
    for (b = 1; b ≤ 10; b++)
        for (c = 1; c ≤ 10; c++)
            for (d = 1; d ≤ 10; d++)
                sum = sum + gcd(gcd(gcd(a, b), c), d);