#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int MOD = 1e9 + 7;

void solve(){
	ll n, k;
	cin >> n >> k;
	
	if(k == 1){
		cout << (n % MOD)<< "\n";
		return;
	}
	ll p = k - 1, q = k - 1;
	
	ll cnt = 2;
	while(q != 0){
		ll next = (p + q);
		next %= k;
		p = q;
		q = next;
		cnt++;
		cnt %= MOD;
	}
	n %= MOD;
	cnt %= MOD;
	n *= cnt;
	n %= MOD;
	cout << n << "\n";
	
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int t = 1;
	cin >> t;
	
	for(int i = 1; i <= t; i++){
		solve();
	}
	return 0;
}