#include<iostream>
#include<cstdio>
#include<algorithm>
#include<complex>
#include<cstring>
#include<cmath>
#include<vector>
#include<map>
#include<unordered_map>
#include<list>
#include<set>
#include<queue>
#include<stack>
#define OldTomato ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
#define fir(i,a,b) for(int i=a;i<=b;++i) 
#define mem(a,x) memset(a,x,sizeof(a))
#define p_ priority_queue
using namespace std;
typedef complex<double> CP;
typedef pair<int,int> PII;
typedef long long ll;
typedef __int128 it;
const double pi = acos(-1.0);
const int INF = 0x3f3f3f3f;
const ll inf = 1e18;
const int N = 2e5+10;
const int M = 1e6+10;
const int mod = 1e9+7;
const double eps = 1e-6;
inline int lowbit(int x){ return x&(-x);}
using namespace std;
template<typename T>void write(T x)
{
	if(x<0)
	{
		putchar('-');
		x=-x;
	}
	if(x>9)
	{
		write(x/10);
	}
	putchar(x%10+'0');
}
template<typename T> void read(T &x)
{
	x = 0;char ch = getchar();ll f = 1;
	while(!isdigit(ch)){if(ch == '-')f*=-1;ch=getchar();}
	while(isdigit(ch)){x = x*10+ch-48;ch=getchar();}x*=f;
}
#define int __int128
int n,m,k,T;
int l,r;
int f1(int n) 
{
	return n*(n+1)*(2*n+1)/6;
}
int f2(int n)
{
	return n*(n+1)/2;
}
int qpow(int a,int k)
{
	int res = 1;
	while(k)
	{
		if(k&1) res = res * a ;
		a = a * a;
		k >>= 1;
	}
	return res;
}
int a[M];
int s[M];
void solve()
{
	read(l); read(r);
	read(k);
	if(k!=1) l -- ;
	int ans = 0;
	if(k == 1)
	{
		ans += (r-l+1) * (l+r)/2;
	}
	else if(k == 2) 
	{
		int idx1 = sqrt((ll)l);
		int idx2 = sqrt((ll)r);
		int res1 = 2 * f1(idx1-1) + f2(idx1-1);
		int res2 = 2 * f1(idx2-1) + f2(idx2-1);
		res1 += (l - qpow(idx1,k) + 1) * (idx1);
		res2 += (r - qpow(idx2,k) + 1) * (idx2);
		ans = res2 - res1;
	}
	else 
	{
		int i = 1;
		for(i=1;;++i)
		{
			a[i] = qpow(i,k);
			if(a[i] > r) break;
			s[i] = s[i-1] + (a[i] - a[i-1]) * (i-1) + 1;
		}
		n = i-1;
		int idx1 = lower_bound(a+1,a+n+1,l) - a;
		idx1 -- ;
		int idx2 = lower_bound(a+1,a+n+1,r) - a;
		idx2 -- ;
		int res1 = s[idx1];
		int res2 = s[idx2];
		res1 += (l - a[idx1]) * (idx1);
		res2 += (r - a[idx2]) * (idx2);
		ans = res2 - res1;
	}
	write(ans);
	cout<<"\n";
}
signed main(void)
{  
	read(T);
	while(T--)
	{
		solve();
	}
	return 0;
}