#include <stdlib.h>   // malloc / 動態配置記憶體
#include <string.h>   // strlen, memcpy / 字串長度與複製

// 回傳數字 d(1..9) 的質因數 2,3,5,7 指數 / prime exponents (2,3,5,7) of digit d
static void digExp(int d, int *a2, int *a3, int *a5, int *a7) {
    int e2 = 0, e3 = 0, e5 = 0, e7 = 0;      // 預設全為 0 / default all zero
    switch (d) {                             // 依數字查表 / lookup by digit
        case 2: e2 = 1; break;               // 2 = 2^1
        case 3: e3 = 1; break;               // 3 = 3^1
        case 4: e2 = 2; break;               // 4 = 2^2
        case 5: e5 = 1; break;               // 5 = 5^1
        case 6: e2 = 1; e3 = 1; break;       // 6 = 2·3
        case 7: e7 = 1; break;               // 7 = 7^1
        case 8: e2 = 3; break;               // 8 = 2^3
        case 9: e3 = 2; break;               // 9 = 3^2
        default: break;                      // 1(或0) 不貢獻 / 1 (or 0) contributes nothing
    }
    *a2 = e2; *a3 = e3; *a5 = e5; *a7 = e7;  // 用指標把結果寫回呼叫端 / write back via pointers
}

// 覆蓋剩餘指數所需的「最少位數」/ minimum digit count to cover the residual exponents
static int minDigits(int r2, int r3, int r5, int r7) {
    if (r2 < 0) r2 = 0; if (r3 < 0) r3 = 0;  // 負數代表已滿足，視為 0 / clamp negatives to 0
    if (r5 < 0) r5 = 0; if (r7 < 0) r7 = 0;
    int e8 = r2 / 3, rem2 = r2 % 3;          // 每個 8 吃掉三個 2 / each 8 absorbs three 2's
    int n9 = r3 / 2, rem3 = r3 % 2;          // 每個 9 吃掉兩個 3 / each 9 absorbs two 3's
    int lc;                                  // 零頭需要的位數 / digits for the leftovers
    if (rem2 == 0 && rem3 == 0) lc = 0;      // 無零頭 / nothing left
    else if (rem2 == 2 && rem3 == 1) lc = 2; // 2^2·3 → 需兩位(如 2,6) / needs two digits
    else lc = 1;                             // 其餘情形一位即可 / one digit otherwise
    return e8 + n9 + lc + r5 + r7;           // 5 與 7 各只能靠 '5','7' / only '5','7' give 5,7
}

// 把「長度剛好 k、覆蓋剩餘指數的最小字串」寫進 dest / write smallest length-k covering string
static void fillSuffix(char *dest, int k, int r2, int r3, int r5, int r7) {
    if (r2 < 0) r2 = 0; if (r3 < 0) r3 = 0;  // 同樣把負值歸零 / clamp negatives
    if (r5 < 0) r5 = 0; if (r7 < 0) r7 = 0;
    int c8 = r2 / 3, rem2 = r2 % 3;          // 8 的個數與 2 的零頭 / count of 8's, leftover 2's
    int c9 = r3 / 2, rem3 = r3 % 2;          // 9 的個數與 3 的零頭 / count of 9's, leftover 3's
    int c2 = 0, c3 = 0, c4 = 0, c6 = 0;      // 零頭湊出的小數字 / small digits from leftovers
    if (rem2 == 1 && rem3 == 0) c2 = 1;      // 剩一個 2 → '2'
    else if (rem2 == 2 && rem3 == 0) c4 = 1; // 剩兩個 2 → '4'(=2^2 只花一位) / one digit
    else if (rem2 == 0 && rem3 == 1) c3 = 1; // 剩一個 3 → '3'
    else if (rem2 == 1 && rem3 == 1) c6 = 1; // 剩一個2一個3 → '6'(併成一位) / merge into 6
    else if (rem2 == 2 && rem3 == 1) { c2 = 1; c6 = 1; } // 2^2·3 → "26" 最小 / smallest
    int c5 = r5, c7 = r7;                     // 5 和 7 直接放 / place 5's and 7's directly
    int m = c2 + c3 + c4 + c5 + c6 + c7 + c8 + c9;  // 有效數字總數 / count of non-1 digits
    int idx = 0;                              // 目前寫到的位置 / current write index
    for (int i = 0; i < k - m; i++) dest[idx++] = '1'; // 多的位補 '1' 放最前(最小) / pad 1's
    for (int i = 0; i < c2; i++) dest[idx++] = '2';    // 之後由小到大輸出 / then ascending
    for (int i = 0; i < c3; i++) dest[idx++] = '3';
    for (int i = 0; i < c4; i++) dest[idx++] = '4';
    for (int i = 0; i < c5; i++) dest[idx++] = '5';
    for (int i = 0; i < c6; i++) dest[idx++] = '6';
    for (int i = 0; i < c7; i++) dest[idx++] = '7';
    for (int i = 0; i < c8; i++) dest[idx++] = '8';
    for (int i = 0; i < c9; i++) dest[idx++] = '9';     // idx 最終等於 k / idx ends at k
}

/* 演算法 / Algorithm:
   1) 把 t 除盡 2,3,5,7；若有殘餘>1 則無解回 "-1"。
   2) num 本身無零且乘積合格就直接回傳。
   3) 否則從右往左找「增大位置」湊出同長度的最小合格數；找不到就用長度 L+1。*/
char* smallestNumber(char* num, long long t) {
    int L = strlen(num);                     // num 的位數 / number of digits
    long long tt = t;                        // 複製 t 來做分解 / copy for factoring
    int e2 = 0, e3 = 0, e5 = 0, e7 = 0;      // 需要的質因數指數 / required exponents
    while (tt % 2 == 0) { tt /= 2; e2++; }   // 除盡 2 / strip factors of 2
    while (tt % 3 == 0) { tt /= 3; e3++; }   // 除盡 3
    while (tt % 5 == 0) { tt /= 5; e5++; }   // 除盡 5
    while (tt % 7 == 0) { tt /= 7; e7++; }   // 除盡 7
    if (tt != 1) {                           // 還有其他質因數 → 不可能整除 / impossible
        char *r = malloc(3); strcpy(r, "-1"); return r;  // 配置並回傳 "-1"
    }

    int z = L;                               // 第一個 '0' 的位置(沒有則 = L) / first zero index
    for (int i = 0; i < L; i++) if (num[i] == '0') { z = i; break; }

    long long T2 = 0, T3 = 0, T5 = 0, T7 = 0;    // 整個 num 的指數總和 / totals over all digits
    for (int i = 0; i < L; i++) {
        int a2, a3, a5, a7; digExp(num[i] - '0', &a2, &a3, &a5, &a7); // num[i]-'0' 由字元轉數字
        T2 += a2; T3 += a3; T5 += a5; T7 += a7;
    }
    if (z == L && T2 >= e2 && T3 >= e3 && T5 >= e5 && T7 >= e7) {  // num 無零且已合格 / valid
        char *r = malloc(L + 1); memcpy(r, num, L); r[L] = '\0'; return r; // 複製一份回傳
    }

    int pmax = (L - 1 < z) ? (L - 1) : z;    // 增大位置最多到第一個 0 / cannot keep a zero
    long long p2 = 0, p3 = 0, p5 = 0, p7 = 0;    // 前綴 num[0..p-1] 的指數 / prefix exponents
    for (int i = 0; i < pmax; i++) {         // 先算 pmax 的前綴指數 / init prefix at p = pmax
        int a2, a3, a5, a7; digExp(num[i] - '0', &a2, &a3, &a5, &a7);
        p2 += a2; p3 += a3; p5 += a5; p7 += a7;
    }

    int bestP = -1, bestD = -1;              // 最佳增大位置與數字 / chosen position & digit
    int BR2 = 0, BR3 = 0, BR5 = 0, BR7 = 0;  // 對應的剩餘指數 / residual exponents for suffix
    for (int p = pmax; p >= 0; p--) {        // 從右往左掃(前綴越長越好) / scan right-to-left
        int dp = num[p] - '0';               // 目前這一位的值 / current digit value
        for (int d = dp + 1; d <= 9; d++) {  // 試最小的、比它大的數字 / smallest larger digit
            int a2, a3, a5, a7; digExp(d, &a2, &a3, &a5, &a7);      // d 的指數 / exps of d
            long long r2 = e2 - p2 - a2, r3 = e3 - p3 - a3;         // 扣掉前綴與 d / subtract
            long long r5 = e5 - p5 - a5, r7 = e7 - p7 - a7;
            int R2 = r2 < 0 ? 0 : (int)r2, R3 = r3 < 0 ? 0 : (int)r3; // 負→0 / clamp
            int R5 = r5 < 0 ? 0 : (int)r5, R7 = r7 < 0 ? 0 : (int)r7;
            int slots = L - 1 - p;           // 後面剩幾個空位 / remaining empty slots
            if (minDigits(R2, R3, R5, R7) <= slots) {   // 塞得下 → 可行 / feasible
                bestP = p; bestD = d;        // 記住答案 / record
                BR2 = R2; BR3 = R3; BR5 = R5; BR7 = R7;
                break;                       // 取最小的 d / take smallest feasible d
            }
        }
        if (bestP != -1) break;              // 取最右(最大)的 p / take right-most feasible p
        if (p - 1 >= 0) {                    // 前綴縮短一位:扣掉 num[p-1] / shrink prefix by 1
            int a2, a3, a5, a7; digExp(num[p - 1] - '0', &a2, &a3, &a5, &a7);
            p2 -= a2; p3 -= a3; p5 -= a5; p7 -= a7;
        }
    }

    if (bestP != -1) {                       // 找到同長度答案 / same-length answer found
        char *r = malloc(L + 1);
        memcpy(r, num, bestP);               // 保留前綴 / keep prefix num[0..bestP-1]
        r[bestP] = (char)('0' + bestD);      // 放入增大後的數字 / place increased digit
        fillSuffix(r + bestP + 1, L - 1 - bestP, BR2, BR3, BR5, BR7); // 填最小後綴 / fill suffix
        r[L] = '\0';                         // 收尾 / null-terminate
        return r;
    }

    int m = minDigits(e2, e3, e5, e7);       // 湊出 t 的最少位數 / min digits to realise t
    int outLen = (L + 1 > m) ? (L + 1) : m;  // 至少比 num 長一位 / at least L+1 (or m)
    char *r = malloc(outLen + 1);
    fillSuffix(r, outLen, e2, e3, e5, e7);   // 前補 1、後放最小數字 / pad 1's then digits
    r[outLen] = '\0';
    return r;
}