import java.io.PrintWriter;

import java.math.BigInteger;

import java.util.Scanner;

public class Main {

    Scanner scan=new Scanner(System.in);

    PrintWriter out=new PrintWriter(System.out);

    BigInteger c[]=new BigInteger[105];

    BigInteger h[][]=new BigInteger[105][105];

    BigInteger n,re;

    int m;

    void getc(){

        c[1]=n;

        for(int i=2;i<=m+1;i++)

            c[i]=c[i-1].multiply(n.subtract(BigInteger.valueOf(i-1))).divide(BigInteger.valueOf(i));

    }

    void run(){

        int cas=scan.nextInt();

        while(cas-- >0){

            n=scan.nextBigInteger().add(BigInteger.ONE);

            m=scan.nextInt();

            getc();

            for(int i=0;i<=m;i++)

                h[0][i]=BigInteger.valueOf(i).pow(m);

            for(int i=1;i<=m;i++)for(int j=0;j<=m-i;j++)

                h[i][j]=h[i-1][j+1].subtract(h[i-1][j]);

            re=BigInteger.ZERO;

            for(int i=0;i<=m;i++)

                re=re.add(c[i+1].multiply(h[i][0]));

            out.println(re);

            out.flush();

        }

    }

    public static void main(String[] args) {

        new Main().run();

    }

}