균일수(codeground)

/*

★모든 b진법으로 N을 나타내본다★

*/

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <vector>

using namespace std;

int main() {

int t;

scanf("%d", &t);

for (int tc = 1; tc <= t; tc++) {

int n;

scanf("%d", &n);

int ans = -1;

for (int b = 2; b*b <= n; b++) {

int num = n%b;

int x = n;

bool ok = true;

while (x > 0) {

if (x%b != num) {

ok = false;

break;

}

x /= b;

}

if (ok) {

ans = b;

break;

}

}

if (ans == -1) {

for (int i = 1; i*i <= n; i++) {

if (n%i != 0) {

continue;

}

int x = i;

int base = n / x - 1;

if (base > x) {

ans = base;

}

}

}

if (ans == -1) {  // 예외처리 N = 1과 2일 때는 답을 구할 수 없다.

ans = n + 1;

}

printf("Case #%d\n", tc);

printf("%d\n", ans);

}

return 0;

}