import java.io.*;
import java.util.*;

public class DrBTreeII {

	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
	static StringTokenizer st = new StringTokenizer("");

	public static String next() {
		try	{
		while (!st.hasMoreTokens()) {
			String s = br.readLine();
			if (s == null)
				return null;
			st = new StringTokenizer(s);
		}
		return st.nextToken();
		}	catch(Exception e)	{
			return	null;
		}
	}
	public static void main(String[] asda) throws Exception {
		mem = new int [1005][1005];
		for (int [] v : mem)	Arrays.fill(v, -1);

		int CASES = Integer.parseInt( next() );
		while	(CASES-- > 0)	{
			int L = Integer.parseInt( next() );
			int K = Integer.parseInt( next() );
			
			int ans = solve(L, K);
			out.println( ans );
		}
        //
        out.flush();
        System.exit(0);
    }

    static final long MOD = 1000000000 + 7, CHARS = 10;
    static int [][] mem;
    static int solve(int len, int mirrors)	{
    	if (len == 0 && mirrors == 0) {
    		return	1;
    	}
    	if (len < 0 || mirrors < 0) {
    		return	0;
    	}

    	if (mem[len][mirrors] != -1) {
    		return mem[len][mirrors];
    	}

    	long ans = 0;
    	if (len % 2 == 1) {
    		// place middle
    		ans = CHARS * solve(len - 1, mirrors - 1);
    		ans %= MOD;
    	}	else	{
    		// place not mirror
    		ans = CHARS * (CHARS - 1) * solve(len - 2, mirrors);
    		ans %= MOD;

    		ans += CHARS * solve(len - 2, mirrors - 1);
    		ans %= MOD;
    	}
    //	out.printf("solve(%d, %d) = %d\n", len, mirrors, ans);
    	return	mem[len][mirrors] = (int)ans;
    }
	
}