#include <vector>
    #include <iostream>
    #include <iomanip>
    #include <queue>
    #include <stack>
    #include <set>
 
    using namespace std;
 
    struct Node
    {
        Node(int i, int p = -1):idx(i),prev(p){}
        int idx;   // Индекс
        int prev;  // Предыдущий узел - для восстановления пути
        bool operator <(const Node& n) const { return idx < n.idx; }
    };
 
    int main()
    {
        int start = 1, stop = 1;
 
        cin >> start;
 
        queue<Node> Q;   // Очередь BFS
        set<Node> S;     // Множество уже обработанных узлов
 
        Q.push(Node(start));
        while(!Q.empty())
        {
            S.insert(Q.front());        // Внесли в обработанные
            int index = Q.front().idx;  // Индекс
            if (index == stop) break;   // Найден!
            Q.pop();                    // Убираем из очереди
            vector<int> next;           // Возможные варианты
            if (index%3 == 0) next.push_back(index/3);
            if (index%2 == 0) next.push_back(index/2);
            if (index > 1) next.push_back(index-1);
            for(int i: next)            // Обработка возможных вариантов
            {
                Node n(i,index);
                if (S.find(n) != S.end()) continue;  // Уже отработан
                Q.push(n);              // Внесение в очередь еще не рассмотренных
            }
        }
 
        // Вывод цепочки - так как в обратном порядке, используем стек
 
        int last = Q.front().idx;
        auto i = S.find(Node(last));
 
        for(int index = i->prev; index != -1; )
        {
            if (index == last * 3) cout << 3; else
            if (index == last * 2) cout << 2; else cout << 1;
            last = index;
            i = S.find(Node(index));    // Поиск предыдущего
            if (i == S.end()) break;         // Береженого Бог бережет :)
            index = i->prev;                 // Предыдущий в цепочке
        }
    }

ICAgICNpbmNsdWRlIDx2ZWN0b3I+CiAgICAjaW5jbHVkZSA8aW9zdHJlYW0+CiAgICAjaW5jbHVkZSA8aW9tYW5pcD4KICAgICNpbmNsdWRlIDxxdWV1ZT4KICAgICNpbmNsdWRlIDxzdGFjaz4KICAgICNpbmNsdWRlIDxzZXQ+CiAgICAKICAgIHVzaW5nIG5hbWVzcGFjZSBzdGQ7CiAgICAKICAgIHN0cnVjdCBOb2RlCiAgICB7CiAgICAgICAgTm9kZShpbnQgaSwgaW50IHAgPSAtMSk6aWR4KGkpLHByZXYocCl7fQogICAgICAgIGludCBpZHg7ICAgLy8g0JjQvdC00LXQutGBCiAgICAgICAgaW50IHByZXY7ICAvLyDQn9GA0LXQtNGL0LTRg9GJ0LjQuSDRg9C30LXQuyAtINC00LvRjyDQstC+0YHRgdGC0LDQvdC+0LLQu9C10L3QuNGPINC/0YPRgtC4CiAgICAgICAgYm9vbCBvcGVyYXRvciA8KGNvbnN0IE5vZGUmIG4pIGNvbnN0IHsgcmV0dXJuIGlkeCA8IG4uaWR4OyB9CiAgICB9OwogICAgCiAgICBpbnQgbWFpbigpCiAgICB7CiAgICAgICAgaW50IHN0YXJ0ID0gMSwgc3RvcCA9IDE7CiAgICAKICAgICAgICBjaW4gPj4gc3RhcnQ7CiAgICAKICAgICAgICBxdWV1ZTxOb2RlPiBROyAgIC8vINCe0YfQtdGA0LXQtNGMIEJGUwogICAgICAgIHNldDxOb2RlPiBTOyAgICAgLy8g0JzQvdC+0LbQtdGB0YLQstC+INGD0LbQtSDQvtCx0YDQsNCx0L7RgtCw0L3QvdGL0YUg0YPQt9C70L7QsgogICAgCiAgICAgICAgUS5wdXNoKE5vZGUoc3RhcnQpKTsKICAgICAgICB3aGlsZSghUS5lbXB0eSgpKQogICAgICAgIHsKICAgICAgICAgICAgUy5pbnNlcnQoUS5mcm9udCgpKTsgICAgICAgIC8vINCS0L3QtdGB0LvQuCDQsiDQvtCx0YDQsNCx0L7RgtCw0L3QvdGL0LUKICAgICAgICAgICAgaW50IGluZGV4ID0gUS5mcm9udCgpLmlkeDsgIC8vINCY0L3QtNC10LrRgQogICAgICAgICAgICBpZiAoaW5kZXggPT0gc3RvcCkgYnJlYWs7ICAgLy8g0J3QsNC50LTQtdC9IQogICAgICAgICAgICBRLnBvcCgpOyAgICAgICAgICAgICAgICAgICAgLy8g0KPQsdC40YDQsNC10Lwg0LjQtyDQvtGH0LXRgNC10LTQuAogICAgICAgICAgICB2ZWN0b3I8aW50PiBuZXh0OyAgICAgICAgICAgLy8g0JLQvtC30LzQvtC20L3Ri9C1INCy0LDRgNC40LDQvdGC0YsKICAgICAgICAgICAgaWYgKGluZGV4JTMgPT0gMCkgbmV4dC5wdXNoX2JhY2soaW5kZXgvMyk7CiAgICAgICAgICAgIGlmIChpbmRleCUyID09IDApIG5leHQucHVzaF9iYWNrKGluZGV4LzIpOwogICAgICAgICAgICBpZiAoaW5kZXggPiAxKSBuZXh0LnB1c2hfYmFjayhpbmRleC0xKTsKICAgICAgICAgICAgZm9yKGludCBpOiBuZXh0KSAgICAgICAgICAgIC8vINCe0LHRgNCw0LHQvtGC0LrQsCDQstC+0LfQvNC+0LbQvdGL0YUg0LLQsNGA0LjQsNC90YLQvtCyCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIE5vZGUgbihpLGluZGV4KTsKICAgICAgICAgICAgICAgIGlmIChTLmZpbmQobikgIT0gUy5lbmQoKSkgY29udGludWU7ICAvLyDQo9C20LUg0L7RgtGA0LDQsdC+0YLQsNC9CiAgICAgICAgICAgICAgICBRLnB1c2gobik7ICAgICAgICAgICAgICAvLyDQktC90LXRgdC10L3QuNC1INCyINC+0YfQtdGA0LXQtNGMINC10YnQtSDQvdC1INGA0LDRgdGB0LzQvtGC0YDQtdC90L3Ri9GFCiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICAKICAgICAgICAvLyDQktGL0LLQvtC0INGG0LXQv9C+0YfQutC4IC0g0YLQsNC6INC60LDQuiDQsiDQvtCx0YDQsNGC0L3QvtC8INC/0L7RgNGP0LTQutC1LCDQuNGB0L/QvtC70YzQt9GD0LXQvCDRgdGC0LXQugogICAgCiAgICAgICAgaW50IGxhc3QgPSBRLmZyb250KCkuaWR4OwogICAgICAgIGF1dG8gaSA9IFMuZmluZChOb2RlKGxhc3QpKTsKICAgIAogICAgICAgIGZvcihpbnQgaW5kZXggPSBpLT5wcmV2OyBpbmRleCAhPSAtMTsgKQogICAgICAgIHsKICAgICAgICAgICAgaWYgKGluZGV4ID09IGxhc3QgKiAzKSBjb3V0IDw8IDM7IGVsc2UKICAgICAgICAgICAgaWYgKGluZGV4ID09IGxhc3QgKiAyKSBjb3V0IDw8IDI7IGVsc2UgY291dCA8PCAxOwogICAgICAgICAgICBsYXN0ID0gaW5kZXg7CiAgICAgICAgICAgIGkgPSBTLmZpbmQoTm9kZShpbmRleCkpOyAgICAvLyDQn9C+0LjRgdC6INC/0YDQtdC00YvQtNGD0YnQtdCz0L4KICAgICAgICAgICAgaWYgKGkgPT0gUy5lbmQoKSkgYnJlYWs7ICAgICAgICAgLy8g0JHQtdGA0LXQttC10L3QvtCz0L4g0JHQvtCzINCx0LXRgNC10LbQtdGCIDopCiAgICAgICAgICAgIGluZGV4ID0gaS0+cHJldjsgICAgICAgICAgICAgICAgIC8vINCf0YDQtdC00YvQtNGD0YnQuNC5INCyINGG0LXQv9C+0YfQutC1CiAgICAgICAgfQogICAgfQ==

NTYyMzQwCg==

562340