import java.util.*;
public class Main{
    static long mod=10000;
    static long[] nums=new long[10001];
    static int b;
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();


        for (int i = 0; i < n; i++) {
            long a=sc.nextInt();
            b=sc.nextInt();
            nums[1]=1;
            for (int k = 2; k <=10000 ; k++) {
                nums[k]=(nums[k-1]+sss(k))%mod;
            }
        System.out.println((int)(n/1.0/mod*nums[10000]+nums[(int)(a%mod)])%mod);
        }
    }
    public static long sss(long t){
        long u=b;
        long sun=1;
        while(u!=0){
            if ((u&1)==1){
                sun=(sun*t)%mod
                ;
            }
            t=(t*t)%mod;
            u=u>>1;
        }
        return sun%mod;
    }
}