#include <string>
#include <array>
#include <algorithm>
using namespace std;

/* 演算法 / Algorithm:
   1) 分解 t 為 2,3,5,7 的指數;有其他質因數則回 "-1"。
   2) num 本身無零且乘積合格就回傳。
   3) 否則右往左找增大位置湊同長度最小合格數;失敗則用長度 L+1。*/
class Solution {
public:
    // 回傳數字 d(1..9) 的 (2,3,5,7) 指數;用 std::array 一次回傳四個值
    // return the (2,3,5,7) exponents of digit d; std::array carries all four at once
    static array<int, 4> digExp(int d) {
        switch (d) {                             // 依數字查表 / lookup by digit
            case 2: return {1, 0, 0, 0};         // 2 = 2^1
            case 3: return {0, 1, 0, 0};         // 3 = 3^1
            case 4: return {2, 0, 0, 0};         // 4 = 2^2
            case 5: return {0, 0, 1, 0};         // 5 = 5^1
            case 6: return {1, 1, 0, 0};         // 6 = 2·3
            case 7: return {0, 0, 0, 1};         // 7 = 7^1
            case 8: return {3, 0, 0, 0};         // 8 = 2^3
            case 9: return {0, 2, 0, 0};         // 9 = 3^2
            default: return {0, 0, 0, 0};        // 1(或0) 無貢獻 / no contribution
        }
    }

    // 覆蓋剩餘指數所需的最少位數 / minimum digit count to cover residual exponents
    static int minDigits(int r2, int r3, int r5, int r7) {
        int e8 = r2 / 3, rem2 = r2 % 3;          // 每個 8 = 三個 2 / each 8 covers three 2's
        int n9 = r3 / 2, rem3 = r3 % 2;          // 每個 9 = 兩個 3 / each 9 covers two 3's
        int lc;                                  // 零頭需要的位數 / digits for leftovers
        if (rem2 == 0 && rem3 == 0) lc = 0;
        else if (rem2 == 2 && rem3 == 1) lc = 2; // 2^2·3 需兩位 / needs two digits
        else lc = 1;
        return e8 + n9 + lc + r5 + r7;           // 5,7 只能各佔一位 / only 5/7 give those primes
    }

    // 回傳「長度剛好 k、覆蓋剩餘指數的最小字串」/ smallest length-k covering string
    static string fillSuffix(int k, int r2, int r3, int r5, int r7) {
        int c8 = r2 / 3, rem2 = r2 % 3;          // 8 的數量與 2 的零頭 / 8's and leftover 2's
        int c9 = r3 / 2, rem3 = r3 % 2;          // 9 的數量與 3 的零頭 / 9's and leftover 3's
        int c2 = 0, c3 = 0, c4 = 0, c6 = 0;      // 零頭湊出的數字 / digits from leftovers
        if (rem2 == 1 && rem3 == 0) c2 = 1;      // '2'
        else if (rem2 == 2 && rem3 == 0) c4 = 1; // '4' 一位覆蓋 2^2 / one digit for 2^2
        else if (rem2 == 0 && rem3 == 1) c3 = 1; // '3'
        else if (rem2 == 1 && rem3 == 1) c6 = 1; // '6' 併掉一個2一個3 / merge 2 and 3
        else if (rem2 == 2 && rem3 == 1) { c2 = 1; c6 = 1; } // "26" 最小 / smallest for 2^2·3
        int m = c2 + c3 + c4 + r5 + c6 + r7 + c8 + c9;  // 有效數字數 / count of non-1 digits
        string s;                                // 用 std::string 累積結果 / build the result
        s.reserve(k);                            // 預留空間避免多次配置 / avoid reallocations
        s.append(k - m, '1');                    // append(n,ch): 補 n 個 '1' 在最前 / pad 1's
        s.append(c2, '2'); s.append(c3, '3'); s.append(c4, '4');  // 之後由小到大 / ascending
        s.append(r5, '5'); s.append(c6, '6'); s.append(r7, '7');
        s.append(c8, '8'); s.append(c9, '9');
        return s;                                // 長度剛好 k / length is exactly k
    }

    string smallestNumber(string num, long long t) {
        int L = num.size();                      // 位數 / number of digits
        long long tt = t;                        // 複製來分解 / copy for factoring
        int e2 = 0, e3 = 0, e5 = 0, e7 = 0;      // 需要的指數 / required exponents
        while (tt % 2 == 0) { tt /= 2; e2++; }   // 除盡各質因數 / strip 2,3,5,7
        while (tt % 3 == 0) { tt /= 3; e3++; }
        while (tt % 5 == 0) { tt /= 5; e5++; }
        while (tt % 7 == 0) { tt /= 7; e7++; }
        if (tt != 1) return "-1";                // 殘餘>1 → 無解 / impossible

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

        long long T2 = 0, T3 = 0, T5 = 0, T7 = 0;    // 整串指數總和 / totals over whole num
        for (char c : num) {                     // range-for: 逐字元走訪 / iterate each char
            auto e = digExp(c - '0');            // auto 讓編譯器推導型別 / deduced array type
            T2 += e[0]; T3 += e[1]; T5 += e[2]; T7 += e[3];
        }
        if (z == L && T2 >= e2 && T3 >= e3 && T5 >= e5 && T7 >= e7)
            return num;                          // num 無零且合格 / already valid

        int pmax = min(L - 1, z);                // 增大位置上限(不可保留 0) / cap at first zero
        long long p2 = 0, p3 = 0, p5 = 0, p7 = 0;    // 前綴指數 / prefix exponents
        for (int i = 0; i < pmax; i++) {         // 初始化為 p=pmax 的前綴 / prefix at pmax
            auto e = digExp(num[i] - '0');
            p2 += e[0]; p3 += e[1]; p5 += e[2]; p7 += e[3];
        }

        int bestP = -1, bestD = -1;              // 最佳位置與數字 / chosen position & digit
        int BR2 = 0, BR3 = 0, BR5 = 0, BR7 = 0;  // 對應剩餘指數 / residual for suffix
        for (int p = pmax; p >= 0; p--) {        // 右往左(前綴越長越小) / right-to-left
            int dp = num[p] - '0';               // 當前位的值 / current digit value
            for (int d = dp + 1; d <= 9; d++) {  // 最小的更大數字 / smallest larger digit
                auto e = digExp(d);              // d 的指數 / exponents of d
                long long r2 = e2 - p2 - e[0], r3 = e3 - p3 - e[1]; // 扣前綴與 d / subtract
                long long r5 = e5 - p5 - e[2], r7 = e7 - p7 - e[3];
                int R2 = max(0LL, r2), R3 = max(0LL, r3);   // 負→0 / clamp to 0
                int R5 = max(0LL, r5), R7 = max(0LL, r7);
                if (minDigits(R2, R3, R5, R7) <= L - 1 - p) {   // 塞得下 / feasible
                    bestP = p; bestD = d;        // 記錄(最小 d) / record smallest d
                    BR2 = R2; BR3 = R3; BR5 = R5; BR7 = R7;
                    break;
                }
            }
            if (bestP != -1) break;              // 取最右可行 p / take right-most p
            if (p - 1 >= 0) {                    // 前綴縮一位 / shrink prefix by one digit
                auto e = digExp(num[p - 1] - '0');
                p2 -= e[0]; p3 -= e[1]; p5 -= e[2]; p7 -= e[3];
            }
        }

        if (bestP != -1) {                       // 同長度答案 / same-length answer
            string ans = num.substr(0, bestP);   // 保留前綴 / keep prefix
            ans += char('0' + bestD);            // 加上增大後的數字 / append increased digit
            ans += fillSuffix(L - 1 - bestP, BR2, BR3, BR5, BR7); // 加最小後綴 / minimal suffix
            return ans;
        }

        int m = minDigits(e2, e3, e5, e7);       // 湊出 t 的最少位數 / min digits for t
        int outLen = max(L + 1, m);              // 必須比 num 長 / must be longer than num
        return fillSuffix(outLen, e2, e3, e5, e7); // 前補 1、後放最小數字 / pad then digits
    }
};