// G. Hagopian solving Kattis sum of square digits

#include <iostream>
#include <vector>
using namespace std;

unsigned ssd(int, int);

int main() {
	int N{}, n{}, b{}, counter = 1;
	cin >> N;
	while (N--) {
		while(cin >> counter >> b >> n)
			cout << counter << " " << ssd(b, n) << endl;
	}
}

unsigned ssd(int b, int n) {
	unsigned sumOfSquareDigits{};
	vector<int> basebCoeffs;
	while (n) {
		//cout << n << "%" << b << " = " << n % b << endl;
		basebCoeffs.push_back(n % b);
		n /= b;
		//cout << n << "/" << b << " = " << n;
	}
	for (int i = 0; i < basebCoeffs.size(); ++i)
		sumOfSquareDigits += basebCoeffs[i] * basebCoeffs[i];
	return sumOfSquareDigits;
}