1 /**
 2 大意  ： 求1^m + 2^m + 3^m + 4^m +....+ n^m
 3 解题步骤：
 4 先构造从0到m的第1阶差分序列，然后以下所有2----》p阶的差分表。
 5 令C[n+1][1]=n,用递推构造C[n+1][1]~C[n+1][p+1]的组合数打个一维表；
 6 最后利用C0*C[1]+C1*C[2]+...+Cp*C[p+1]得出答案...
 7 注意: java 提交时，一定要将包名去掉，，并且类名为Main
 8 这一题就是因为多加了个包名，，一直是 runtime error。。一个多小时。。血的教训啊。。
 9 
10 **/
11 
12 import java.io.OutputStreamWriter;
13 import java.io.PrintWriter;
14 import java.math.BigInteger;
15 import java.util.Scanner;
16 
17 public class Main {
18        
19         static BigInteger h[][] = new BigInteger [150][150];
20         static BigInteger []c = new BigInteger [150];
21         public static void getc(BigInteger n,int m){
22                c[1] =n;
23                for(int i=2 ; i<=m+1 ; i++ ){
24                       c[i]= c[i-1].multiply(n.subtract(BigInteger.valueOf(i-1))).divide(BigInteger. valueOf(i));
25               }
26               
27        }
28        
29         public static void main(String[] args) {
30               Scanner cin = new Scanner(System. in);
31                int t = cin.nextInt();
32                while(t-->0){
33                      BigInteger n = cin.nextBigInteger().add(BigInteger. ONE);
34                       int m = cin.nextInt();
35                       for(int i=0; i<=m;i++)
36                             h[0][i] = BigInteger. valueOf(i).pow(m);
37                      
38                       for(int i=1;i<=m;i++){
39                             for(int j=0;j<=m-i;j++){
40                                    h[i][j] = h[i-1][j+1].subtract( h[i-1][j]);
41                            }
42                      }
43                      BigInteger ans = BigInteger. ZERO;
44                       getc(n,m);
45                       for(int i=0;i<=m;i++){
46                            ans = ans.add( h[i][0].multiply( c[i+1]));
47                      }             
48                      System. out.println(ans);
49               }
50 
51        }
52 
53 }