UVa 10677 - Base Equality

// UVa 10677 - Base Equality

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

#define integer unsigned long long

vector<int> tobase(int b, integer n) {
	vector<int> v;
	while (n) {
		v.push_back(n % b);
		n /= b;
	}
	return v;
}

integer frombase(int b, vector<int> v) {
	integer n = 0;
	for (int k = v.size() - 1; k >= 0; k--)
		n = n * b + v[k];
	return n;
}

int main() {
	int t;
	for (cin >> t; t; t--) {
		int b1, b2, r1, r2;
		cin >> b1 >> b2 >> r1 >> r2;
		bool found = false;
		for (int r = r2; r >= r1; r--) {
			vector<int> n1 = tobase(b1, r);
			integer n2 = frombase(b2, n1);
			if (n2 % r == 0) {
				cout << r << endl;
				found = true;
				break;
			}
		}
		if (!found)
			cout << "Non-existent." << endl;
	}
	return 0;
}