// Arup Guha
// 7/14/2025
// Solution to 2025 SI@UCF CP Camp Contest #2 Problem: Divisble Subset Quest

import java.util.*;

public class divisible {

	final public static long MOD = 1000000007;
	
	public static void main(String[] args) {
	
		Scanner stdin = new Scanner(System.in);
		int nC = stdin.nextInt();
		
		// Process cases.
		for (int loop=0; loop<nC; loop++) {
			int n = stdin.nextInt();
			int d = stdin.nextInt();
			System.out.println(solve(n, d));
		}
	}
	
	public static long solve(int n, int d) {
	
		long[] res = new long[d];
		res[0] = 1;
		
		for (int i=1; i<=n; i++) {
		
			// All subsets without i.
			long[] tmp = new long[d];
			for (int j=0; j<d; j++)
				tmp[j] = res[j];
				
			for (int j=0; j<d; j++)
				tmp[(i+j)%d] = (tmp[(i+j)%d] + res[j])%MOD;
				
			res = tmp;
		}
		
		return res[0];
	
	}
}