/**

 大意  ： 求1^m + 2^m + 3^m + 4^m +....+ n^m

 解题步骤：

 先构造从0到m的第1阶差分序列，然后以下所有2----》p阶的差分表。

 令C[n+1][1]=n,用递推构造C[n+1][1]~C[n+1][p+1]的组合数打个一维表；

 最后利用C0*C[1]+C1*C[2]+...+Cp*C[p+1]得出答案...

 注意: java 提交时，一定要将包名去掉，，并且类名为Main

 这一题就是因为多加了个包名，，一直是 runtime error。。一个多小时。。血的教训啊。。

 **/

 import java.io.OutputStreamWriter;

 import java.io.PrintWriter;

 import java.math.BigInteger;

 import java.util.Scanner;

 public class Main {

         static BigInteger h[][] = new BigInteger [][];

         static BigInteger []c = new BigInteger [];

         public static void getc(BigInteger n,int m){

                c[] =n;

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

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

               }

        }

         public static void main(String[] args) {

               Scanner cin = new Scanner(System. in);

                int t = cin.nextInt();

                while(t-->){

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

                       int m = cin.nextInt();

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

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

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

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

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

                            }

                      }

                      BigInteger ans = BigInteger. ZERO;

                       getc(n,m);

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

                            ans = ans.add( h[i][].multiply( c[i+]));

                      }

                      System. out.println(ans);

               }

        }

 }