#include <bits/stdc++.h>

using namespace std;
using LL = long long;
using PII = pair<LL , int> ;
using ULL = unsigned long long;

const int N = 3e2 + 10 , M = 6e4 + 10, Mod = 998244353 , P = 131;


void solved() {

    LL n , k;
    cin >> n >> k;


    LL t;
    auto check = [&](int b){
        LL nn = n / t;
        LL sum = 0;
        for(int i = 1 ; i <= k ; i ++ ){
            // (b + t) ^ (k - i) * b ^ (i - 1)
            LL res = 1;
            for(int j = 1 ; j <= (k - i) ; j ++ ){
                if((__int128)res * (b + t) > nn) return 2;
                res *= (b + t);
            }
            LL ans = 1;
            for(int j = 1 ; j <= i - 1 ; j ++ ){
                if((__int128)ans * b > nn) return 2;
                ans *= b;
            }
            if((__int128)ans * res > nn) return 2;
            if((__int128)sum + ans * res > nn) return 2;
            sum += ans * res;
        }
        if(sum == nn) return 1;
        return 0;
    };

    int ans = 0;
    for(t = 1 ; t * t <= n / t ; t ++ ){

        if(n % t) continue;

        if(k == 3){
            LL deta = 9 * t * t - 12 * (t * t - n / t);

            if(deta < 0)
                continue;
            double x1 = (double)(-3 * t + sqrt(deta)) / 6;
            if(x1 > 0 && x1 == (int)x1) ans ++;
            continue;
        }

        int l = 1 , r = 1e6;
        while (l < r){
            int mid = (l + r) >> 1;
            if(check(mid)) r = mid;
            else l = mid + 1;
        }
        if(check(l) == 1) ans ++;
    }

    cout << ans << "\n";
}

int main(){

//      freopen("D:\\dev\\code\\sunwking\\1.in" , "r" , stdin);

    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);


    int t = 1;
    cin >> t;

    while(t -- )
        solved();


    return 0;
}