#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <stdexcept>
#include <string>
#include <unistd.h>
#include <unordered_set>
#include <vector>
#include <boost/multiprecision/gmp.hpp>

const char *minidc_e(const char *src, std::string &output) {
    using boost::multiprecision::mpz_int;
    using boost::multiprecision::powm;
    using boost::multiprecision::pow;
    int I = 10, O = 10;
    std::vector<mpz_int> stack;
    output.clear();
    
    auto push = [&](mpz_int d) { stack.push_back(d); };
    auto pop =  [&]() -> mpz_int {
        if(stack.empty()) throw std::logic_error("stack underflow");
        auto r = stack.back();
        stack.pop_back();
        return r;
    };

    auto parse_literal = [&](const char *&src) {
        mpz_int r = 0;
        while( (*src >= 'A' && *src <= 'F') ||
                (*src >= '0' && *src <= '9')) {
            if(*src >= '0' && *src  <= '9')
                r = r * I + *src++ - '0';
            else
                r = r * I + *src++ - 'A' + 10;
        }
        src--;
        return r;
    };

    auto to_string = [&](mpz_int d) {
        if(d == 0) { output += "0"; }
        if(d < 0) { output += "-"; d = -d; }
        auto first = output.size();
        while(d) {
            auto i = int(d % O); d /= O;
            if(i < 10) output += ('0' + i);
            else output += ('A' + i - 10);
        }
        std::reverse(output.begin() + first, output.end());
    };

#define BINOP(CODE,OP) \
    case CODE: { auto a = pop(); auto b = pop(); push(b OP a); } break

    while(*src) {
        switch(*src) {
        case '0': case '1': case '2': case '3': case '4': case '5':
        case '6': case '7': case '8': case '9':
        case 'A': case 'B': case 'C': case 'D': case 'E': case 'F':
            push(parse_literal(src)); break;
        case 'I': push(I); break;
        case 'O': push(O); break;
        case 'd': { auto a = pop(); push(a); push(a); break; }
        case 'i': {
            auto a = pop();
            if(a < 2 || a > 16) return "bad input radix";
            I = int(a); break;
        }
        case 'n': to_string(pop()); break;
        case 'o': {
            auto a = pop();
            if(a < 2 || a > 16) return "bad output radix";
            O = int(a); break;
        }
        case 'p': to_string(pop()); output += "\n"; break;
        case 'r': { auto a = pop(); auto b = pop(); push(a); push(b); break; }
        BINOP('*', *);
        BINOP('+', +);
        BINOP('-', -);
        case '/': {
            auto a = pop();
            auto b = pop();
            if(!a) return "division by zero";
            push(b / a);
            break;
        }
        case '~': {
            auto a = pop();
            auto b = pop();
            if(!a) return "division by zero";
            push(b / a);
            push(b % a);
            break;
        }
        case '^': {
            auto a = pop();
            auto b = pop();
            if(a > 10000) return "exponent too large";
            if(a < 0) return "exponent negative";
            if(!isfinite(std::pow(double(b), double(a))))
                return "exponent too large";
            push(boost::multiprecision::pow(b, int(a)));
            break;
        }
        case 'v': {
            auto a = pop();
            if(a < 0) return "square root of negative";
            push(sqrt(a));
            break;
        }
        case '|': {
            auto a = pop();
            auto b = pop();
            auto c = pop();
            if(!a) return "zero reduction modulus";
            if(b < 0) return "negative exponent";
            if(c < 0)
                return "negative base (dc interprets incompatibly to minidc)";
            push(powm(c, b, a));
            break;
        }
        case 'z':
            push(stack.size()); break;

        case ' ': case '\n': case '\t': break;
        default: throw std::logic_error(std::string("unknown opcode ") + *src);
        }
        src++;
    }
    return output.c_str();
}

const char *minidc(const char *src, std::string &work) {
    try {
        return minidc_e(src, work);
    } catch(const std::logic_error &e) {
        return (work = e.what()).c_str();
    }
}

std::unordered_set<int> seen;

struct charset {
    char c;
    int8_t minstack;
    int8_t dstack;
};

const charset charset[] = {
    {' ', 0, 0},
    {'~', 2, 0},
    {'^', 2, -1},
    {'-', 2, -1},
    {'/', 2, -1},
    {'*', 2, -1},
    {'+', 2, -1},
    {'|', 3, -2},
    {'A', -1, 0},
    {'B', -1, 0},
    {'C', -1, 0},
    {'D', -1, 0},
    {'d', 1, 1},
    {'E', -1, 0},
    {'F', -1, 0},
    {'I', 0, 1},
    {'i', 1, -1},
    {'n', 1, -1},
    {'O', 0, 1},
    {'o', 1, -1},
    {'r', 2, 0},
    {'v', 1, 0},
    {'z', 0, 1},
};

char c[100];

static void spinner(const char *s, const char *w) {
    static unsigned long long i = 0, j = 1000;
    if(++i % j == 0) {
        fprintf(stderr, "%16lld [%14s] [%14.14s] %zd\r", i, s, w, seen.size()); fflush(stderr);
        if(i == j * 10 && j < 1000000) j *= 10;
    }
}

static void test(const char *p) {
    static std::string work;
    auto s = minidc(p, work);
    spinner(p, work.c_str());
    try {
        size_t pos;
        auto i = std::stoi(s, &pos);
        if(s[pos]) return;
        if(i < 0 || i > 1000000) return;
        auto r = seen.insert(i);
        if(r.second) 
        {
#ifndef VERIFY
            printf("%7d %s\n", i, p);
#else
            printf("%7d ", i);
            fflush(stdout);
            char buf[300];
            snprintf(buf, sizeof(buf), "echo '%s' | dc 2>&1", p);
            system(buf);
            printf(" %s\n", p);
#endif
            fflush(stdout);
        }
    } catch(std::exception &e) {}
}

static
void doit(char *st, char *pos, int n, int d) {
    if(n == 0) {
        pos[0] = 'n';
        pos[1] = '\0';
        test(st);
        return;
    }
    for(const auto &c : charset) {
        if(d < c.minstack) continue;
        auto newd = d + c.dstack;
        auto lastdig = (pos[-1] >= 'A' && pos[-1] <= 'F');
        if(c.c == ' ' && !lastdig) continue;
        if(c.minstack == -1 && !lastdig) newd ++;
        *pos = c.c;
        doit(st, pos+1, n-1, newd);
    }
    *pos = 0;
}

int main(int argc, char **argv) {
    if(argc == 1) {
        c[0] = ' ';
        for(int i=1; i<11; i++) {
            doit(c+1, c+1, i, 0);
        }
    } else {
        for(int i=1; i<argc; i++) {
            std::string work;
            printf("%-14s [%2zd]: %s\n", argv[i], strlen(argv[i]), minidc(argv[i], work));
        }
    }
}