#include <bits/stdc++.h>
using namespace std;

typedef unsigned long long ull;
const ull LIMIT = (1ULL << 63) - 1;

int B;
ull N;
vector<ull> c; // Các thừa số có thể dùng (ước của N, < B)
vector<ull> best_digits; // Kết quả tốt nhất (số lượng ít nhất)

// So sánh 2 vector đại diện cho số chữ số (số lượng ít hơn thì tốt hơn)
// Nếu số lượng bằng, ta cần so sánh giá trị số học, nhưng do bước sau sort giảm dần,
// chỉ cần so sánh số lượng là đủ để prune.
bool is_better(const vector<ull>& a, const vector<ull>& b) {
    if (a.size() != b.size()) return a.size() < b.size();
    // Nếu số lượng bằng, ta không prune mà để phép DFS tìm tất cả cách phân tích,
    // sau đó chọn cách tạo ra số X nhỏ nhất.
    // Tuy nhiên, để tối ưu, ta chỉ cần tìm cách có số lượng chữ số ít nhất.
    // Nếu có nhiều cách cùng số lượng chữ số, ta phải so sánh X.
    return false;
}

// Tạo số X từ các chữ số
ull make_number(vector<ull>& digits) {
    sort(digits.rbegin(), digits.rend()); // Sắp xếp giảm dần để X nhỏ nhất
    ull res = 0;
    for (ull d : digits) {
        if (res > LIMIT / B) return 0; // Overflow
        res = res * B + d;
    }
    return res;
}

void dfs(ull n, vector<ull>& current_digits) {
    if (n == 1) {
        ull candidate = make_number(current_digits);
        if (candidate == 0) return; // Quá giới hạn
        if (best_digits.empty() || candidate < make_number(best_digits)) {
            best_digits = current_digits;
        }
        return;
    }

    // Pruning: Nếu số lượng chữ số hiện tại >= số lượng tốt nhất đã tìm được, dừng.
    if (!best_digits.empty() && current_digits.size() >= best_digits.size()) return;

    // Thử các thừa số từ lớn đến nhỏ để giảm số lượng chữ số
    for (int i = c.size() - 1; i >= 0; --i) {
        ull d = c[i];
        if (n % d == 0) {
            current_digits.push_back(d);
            dfs(n / d, current_digits);
            current_digits.pop_back();
        }
    }
}

void solve() {
    if (!(cin >> B >> N)) return;
    c.clear();
    best_digits.clear();

    // Tìm các ước của N nhỏ hơn B
    for (ull i = 2; i * i <= N; ++i) {
        if (N % i == 0) {
            if (i < B) c.push_back(i);
            ull j = N / i;
            if (j != i && j < B) c.push_back(j);
        }
    }
    if (N < B) c.push_back(N);

    // Bước quan trọng: Gộp các thừa số cơ số để tạo số lớn hơn, giảm số lượng chữ số
    // Ví dụ: 2*2*2 = 8 (nếu 8 < B)
    // Thay vì dùng DFS gộp, ta có thể tạo list các số composite < B là ước của N
    // Tuy nhiên, cách đơn giản và hiệu quả là dùng DFS chia N, ưu tiên các thừa số lớn.
    // Do N < 2^63, số lượng ước không quá lớn (khoảng vài nghìn). DFS chia N là khả thi.

    // Sắp xếp c tăng dần để khi backtracking thử từ cuối (lớn nhất) xuống trước
    sort(c.begin(), c.end());

    vector<ull> cur;
    dfs(N, cur);

    if (best_digits.empty()) {
        cout << "NO SOLUTION" << endl;
    } else {
        ull ans = make_number(best_digits);
        cout << ans << endl;
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int t;
    if (cin >> t) {
        while(t--) solve();
    } else {
        // Đọc đến EOF
        while(cin >> B >> N) solve();
    }
    return 0;
}

// Skeleton cho DP approach
// Cần map lưu trữ kết quả: map<pair<ull, bool>, ull> dp;
// dp[n][is_first] trả về số chữ số tối thiểu để tạo ra n, hoặc -1 nếu không thể.
// is_first giúp xử lý trường hợp chữ số đầu tiên không được là 0 (nhưng ở đây N>0 nên không có chữ số 0).
// Tuy nhiên, do N lớn, cần tối ưu.

ull solve_dp(ull n, bool is_first) {
    if (n < B) return 1;
    if (dp.count({n, is_first})) return dp[{n, is_first}];
    ull best = -1; // -1 biểu thị vô nghiệm
    // Thử các thừa số d
    for (ull d : valid_digits) {
        if (n % d == 0) {
            ull sub = solve_dp(n / d, false);
            if (sub != -1) {
                if (best == -1 || sub + 1 < best) best = sub + 1;
            }
        }
    }
    return dp[{n, is_first}] = best;
}

// Sau khi có số lượng chữ số tối thiểu, ta cần tìm cách tạo X nhỏ nhất.
// Ta có thể làm 2 bước:
// 1. DP để tìm min số chữ số.
// 2. DFS lại để tạo số X nhỏ nhất với đúng số lượng chữ số đó.

// Bước tiền xử lý để giảm số lượng thừa số
// Thay vì dùng tất cả ước < B, ta chỉ dùng các ước mà không thể chia đôi bởi các ước khác < B
// Ví dụ: Nếu 2, 4, 8 đều là ước và 8 < B, ta loại 2 và 4 vì 8 hiệu quả hơn.

vector<ull> get_optimized_factors(ull N, int B) {
    vector<ull> raw;
    for (ull i = 2; i * i <= N; ++i) {
        if (N % i == 0) {
            if (i < B) raw.push_back(i);
            ull j = N / i;
            if (j < B && j != i) raw.push_back(j);
        }
    }
    if (N < B) raw.push_back(N);
    sort(raw.begin(), raw.end());

    vector<ull> optimized;
    // Duyệt từ lớn đến nhỏ, loại bỏ các số chia hết cho số đã chọn
    vector<bool> used(raw.size(), false);
    for (int i = raw.size() - 1; i >= 0; --i) {
        bool can_use = true;
        for (int j = 0; j < optimized.size(); ++j) {
            if (optimized[j] % raw[i] == 0) {
                can_use = false;
                break;
            }
        }
        if (can_use) optimized.push_back(raw[i]);
    }
    return optimized;
}

// Sử dụng optimized factors trong DFS