#include<iostream>
#include<cstring>
#include<fstream>
#include<cstdio>
#include<cstdlib>
using namespace std;
ifstream fin("piggy.in");
ofstream fout("piggy.out");
 
int T,n,m;int f[55][55][105]={0},ans[105];
 
void Print(int a[]){
     int i=100;
     while(i>0&&a[i]==0) i--;
     while(i>=0) fout<<a[i--];
     fout<<endl;
     }
 
void Init(){
     for(int i=1;i<=50;++i)
     for(int j=1;j<=i;++j)
     {
       if(j==i||j==1) {f[i][j][0]=1;continue;}
       for(int k=0;k<=100;++k)
       f[i][j][k]=f[i-1][j][k]*j;
       for(int k=0;k<=100;++k)
       f[i][j][k]+=f[i-1][j-1][k];
       for(int k=0;k<=100;++k)
       if(f[i][j][k]>9)
       {f[i][j][k+1]+=f[i][j][k]/10;f[i][j][k]%=10;}
             }
     
  /*   for(int i=1;i<=100;++i)
     for(int j=0;j<=i;++j)
     {
       if(j==i||j==0) {c[i][j][0]=1;continue;}
       for(int k=0;k<=100;++k)
       c[i][j][k]=c[i-1][j-1][k]+c[i-1][j][k];
       for(int k=0;k<=100;++k)
       if(c[i][j][k]>9) {c[i][j][k+1]+=c[i][j][k]/10;c[i][j][k]%=10;}
             }*/
 /*    for(int i=1;i<=10;++i,cout<<endl)
     for(int j=0;j<=i;++j)
     Print(c[i][j]);system("pause");  */
     }
 
/*void Chu(){
     while(m>1)
     {
       int tot=0;
       for(int i=100;i>=0;--i)
       {
         int t=ans[i];
         ans[i]=(ans[i]+tot*10)/m;
         tot=(t+tot*10)%m;
               }
       m--;    
               }
     }
*/
int main()
{
    Init();
    fin>>T;
    
   
    while(T>0)
    {
      T--;
    //  memset(ans,0,sizeof(ans));
      fin>>n>>m;
     // if(n==m) {cout<<1<<endl;continue;}
    //  for(int i=0;i<=100;++i)
    //  ans[i]=c[n][m][i];
      
   /*   int k=n-m;
      while(k>0)
      {
        k--;
        for(int i=0;i<=100;++i)
        ans[i]*=m;
        for(int i=0;i<=100;++i)
        if(ans[i]>9) {ans[i+1]+=ans[i]/10;ans[i]%=10;}
                }
      Chu();*/
      Print(f[n][m]);
              }
    
    //system("pause");
    }