#define ll long long
#define pii pair <int,int>
#define mp make_pair
#define pb push_back

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <queue>
#include <cassert>


using namespace std;

const ll INF = (1LL<<31);
const int N = 10;

int a[N],p[N];
int n,m;
map<int,int>hash;
map<int,int>::iterator it;
vector< pii >u,v;
ll ans;
ll TINF;

struct HT
{

    int *T,*C,m;
    HT(int m=3375007)
    {
        this->m=m;
        T=new int[m];
        C=new int[m];
    }

    void clear()
    {
        memset(T,-1,m*sizeof(int));
    }


    int h( int k,int i )
    {
        //h1+i*h2
        return (m + ( (k%m) + (ll)i*( 1+(k% (m-1) ) ) ) )%m;
    }

    void insert(int k )
    {
        int i=0,j;
        while( i!=m )
        {
            j=h( k,i );
            if( T[j]==-1 ){T[j]=k,C[j]=1;return;}
            else if( T[j]==k ){C[j]++;return;}
            else i=i+1;
        }
    }
    int search( int k )
    {
        int i=0,j;
        while( i!=m  )
        {
            j=h( k,i );
            if( T[j]==-1 )return 0;
            else if( T[j]==k )return C[j];
            else i=i+1;
        }
        return 0;
    }
    ~HT()
    {
        delete T;
    }
};

HT H;
ll myabs( ll a )
{
    if(a<0)a=-a;
    return a;
}
ll dp[155][32];
ll pow( int x,int n )
{
    if(x==1)return 1;
    if( dp[x][n]!=-1 )return dp[x][n];
    ll ret=1;
    for(int i=0;i<n;i++)ret*=x;
    return dp[x][n]=ret;
}
void f1( int p,ll s )
{



    if( p==v.size() )
    {

        H.insert( (int)s );
       // cout<<endl;
       // hash[ (int)s ]++;
        return;
    }


    ll ns;



    for( int i=1;i<=m;i++ )
    {
        ns=s+ v[ p ].first * (ll)pow( i, v[p].second );
        if( myabs(ns)>=INF )break;
        f1( p+1,ns );
    }


    return;

}


void f2( int p,ll s )
{
    if( p==u.size() )
    {
        ans+=H.search( (int)s );
       // it=hash.find( (int)s );
       // if( it!=hash.end() )ans+=it->second;
        return;
    }


    ll ns;
    for( int i=1;i<=m;i++ )
    {
        ns=s+ u[ p ].first * (ll)pow( i, u[p].second );
        if( myabs(ns)>=INF )break;
        f2( p+1,ns );
    }


    return;

}




int main()
{


    //freopen("in.txt","r",stdin);

    int T,i,j,k,x,y;
    cin>>T;

    memset( dp,-1,sizeof(dp) );

    while(T--)
    {
        cin>>n>>m;


        for( i=0,j=0;i<n;i++ )
        {
            cin>>a[i]>>p[i];
        }

        u.clear();
        v.clear();

        for( i=0;i<n/2;i++ )
        {
            v.pb( mp( -a[i],p[i] ) );
        }
        for(;i<n;i++)
        {
            u.pb( mp( a[i],p[i] ) );
        }

        //hash.clear();
        H.clear();

        ans=0;

        f1(0,0);
        f2(0,0);




        cout<<ans<<endl;




    }

    return 0;
}


/*
123
6 150
1 1
1 1
1 1
-1 1
-1 1
-1 1
*/