import java.util.Scanner;
 
//mevius.5ch.net/test/read.cgi/tech/1480579110/909
class Q9_909_2
{
    public static void main(String[] args)
    {
        try (Scanner in = new Scanner(System.in))
        {
            int b = in.nextInt();
            String v = in.next();
            long l = 0;
            for (int i = 0; i < v.length(); i++)
            {
                l *= b;
                int c = v.charAt(i);
                if (c >= '0' && c <= '9') l += c - '0';
                else if (c >= 'a' && c <= 'z') l += c - 'a' + 10;
                else if (c >= 'A' && c <= 'Z') l += c - 'A' + 10;
                else throw new IllegalArgumentException();
            }
 
            for (int i = 2; i <= 36; i++)
            {
                System.out.printf("%d#%s%n", i, toString(l, i));
            }
        }
    }
 
 
    static char[] cs = "0123456789abcdefghijklmnopqrstuvwxyz".toCharArray();
    static String toString(long l, int b)
    {
        if (l == 0) return "0";
        StringBuilder sb = new StringBuilder();
        while (l != 0)
        {
            sb.append(cs[(int) (l % b)]);
            l /= b;
        }
        return sb.reverse().toString();
    }
}

aW1wb3J0IGphdmEudXRpbC5TY2FubmVyOwoKLy9tZXZpdXMuNWNoLm5ldC90ZXN0L3JlYWQuY2dpL3RlY2gvMTQ4MDU3OTExMC85MDkKY2xhc3MgUTlfOTA5XzIKewogICAgcHVibGljIHN0YXRpYyB2b2lkIG1haW4oU3RyaW5nW10gYXJncykKICAgIHsKICAgICAgICB0cnkgKFNjYW5uZXIgaW4gPSBuZXcgU2Nhbm5lcihTeXN0ZW0uaW4pKQogICAgICAgIHsKICAgICAgICAgICAgaW50IGIgPSBpbi5uZXh0SW50KCk7CiAgICAgICAgICAgIFN0cmluZyB2ID0gaW4ubmV4dCgpOwogICAgICAgICAgICBsb25nIGwgPSAwOwogICAgICAgICAgICBmb3IgKGludCBpID0gMDsgaSA8IHYubGVuZ3RoKCk7IGkrKykKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgbCAqPSBiOwogICAgICAgICAgICAgICAgaW50IGMgPSB2LmNoYXJBdChpKTsKICAgICAgICAgICAgICAgIGlmIChjID49ICcwJyAmJiBjIDw9ICc5JykgbCArPSBjIC0gJzAnOwogICAgICAgICAgICAgICAgZWxzZSBpZiAoYyA+PSAnYScgJiYgYyA8PSAneicpIGwgKz0gYyAtICdhJyArIDEwOwogICAgICAgICAgICAgICAgZWxzZSBpZiAoYyA+PSAnQScgJiYgYyA8PSAnWicpIGwgKz0gYyAtICdBJyArIDEwOwogICAgICAgICAgICAgICAgZWxzZSB0aHJvdyBuZXcgSWxsZWdhbEFyZ3VtZW50RXhjZXB0aW9uKCk7CiAgICAgICAgICAgIH0KCiAgICAgICAgICAgIGZvciAoaW50IGkgPSAyOyBpIDw9IDM2OyBpKyspCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIFN5c3RlbS5vdXQucHJpbnRmKCIlZCMlcyVuIiwgaSwgdG9TdHJpbmcobCwgaSkpOwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgfQoKCiAgICBzdGF0aWMgY2hhcltdIGNzID0gIjAxMjM0NTY3ODlhYmNkZWZnaGlqa2xtbm9wcXJzdHV2d3h5eiIudG9DaGFyQXJyYXkoKTsKICAgIHN0YXRpYyBTdHJpbmcgdG9TdHJpbmcobG9uZyBsLCBpbnQgYikKICAgIHsKICAgICAgICBpZiAobCA9PSAwKSByZXR1cm4gIjAiOwogICAgICAgIFN0cmluZ0J1aWxkZXIgc2IgPSBuZXcgU3RyaW5nQnVpbGRlcigpOwogICAgICAgIHdoaWxlIChsICE9IDApCiAgICAgICAgewogICAgICAgICAgICBzYi5hcHBlbmQoY3NbKGludCkgKGwgJSBiKV0pOwogICAgICAgICAgICBsIC89IGI7CiAgICAgICAgfQogICAgICAgIHJldHVybiBzYi5yZXZlcnNlKCkudG9TdHJpbmcoKTsKICAgIH0KfQ==

MTYgZGVhZGJhYmU=

16 deadbabe