import java.util.*;

public class ExtremeFibonacci {
	public static long fib(long n){
		if(n < 2) return 1;
		return fib(n-2) + fib(n-1);
	}

	public static long fib(int n, int k){
		long f0 = 1;
		long f1 = 1;
		for(int i=2;i<=n;i++){
			long tmp = f1;
			f1 = f0 + f1;
			f0 = tmp;	
			f1 = f1 % (long) Math.pow(10,k);
			f0 = f0 % (long) Math.pow(10,k);
		}
		return f1;
	}
	
	static int numberSize(long n){
		return (n + "").length();
	}
	public static String formatResult(long res, int k){
		int zeros = k - numberSize(res);
		StringBuffer sb = new StringBuffer();
		sb.append(res);
		for(int i=0;i<zeros;i++)
			sb.insert(0,'0');
		return sb.toString();
	}
	
	public static void main(String[] args){
		String input ="4\n1 1\n5 3\n100 4\n1000 5";
		Scanner s = new Scanner( input);
		int cases = s.nextInt();
		for(int i=0;i<cases;i++){
			int n = s.nextInt();
			int k = s.nextInt();
			String res = formatResult( fib(n,k),k );					
			System.out.println(res);
		}
	}
}