PLACES=['Afghanistan','Albania','Algeria','Samoa','Andorra','Angola','Anguilla','Antarctica','Antigua','Barbuda','Argentina','Armenia','Aruba','Australia','Austria','Azerbaijan','Bahamas','Bahrain','Bangladesh','Barbados','Belarus','Belgium','Belize','Benin','Bermuda','Bhutan','Bolivia','Bosnia','Herzegovina','Botswana','Bouvet','Brazil','Brunei','Darussalam','Bulgaria','Burkina','Faso','Burundi','Cambodia','Cameroon','Canada','Verde','Cayman','Chad','Chile','China','Colombia','Comoros','Congo','Costa','Rica','Croatia','Cuba','Cyprus','Czech','Denmark','Djibouti','Dominica','Ecuador','Egypt','Salvador','Guinea','Eritrea','Estonia','Ethiopia','Falklands','Faroe','Fiji','Finland','France','Guiana','Polynesia','Gabon','Gambia','Georgia','Germany','Ghana','Gibraltar','Greece','Greenland','Grenada','Guadeloupe','Guam','Guatemala','Guinea','Bissau','Guyana','Haiti','Honduras','Hungary','Iceland','India','Indonesia','Iran','Iraq','Ireland','Israel','Italy','Jamaica','Japan','Jordan','Kazakhstan','Kenya','Kiribati','Kuwait','Kyrgyzstan','Laos','Latvia','Lebanon','Lesotho','Liberia','Libya','Liechtenstein','Lithuania','Luxembourg','Macau','Macedonia','Madagascar','Malawi','Malaysia','Maldives','Mali','Malta','Martinique','Mauritania','Mauritius','Mayotte','Mexico','Moldova','Monaco','Mongolia','Montserrat','Morocco','Mozambique','Myanmar','Namibia','Nauru','Nepal','Netherlands','Caledonia','Zealand','Nicaragua','Niger','Nigeria','Niue','Korea','Mariana','Norway','Oman','Pakistan','Palau','Palestine','Panama','Papua','Paraguay','Peru','Philippines','Pitcairn','Poland','Portugal','Puerto','Rico','Qatar','Reunion','Romania','Russia','Rwanda','Samoa','Marino','Saudi','Arabia','Senegal','Seychelles','Sierra','Leone','Singapore','Slovakia','Slovenia','Somalia','Spain','Sudan','Suriname','Swaziland','Sweden','Switzerland','Syria','Taiwan','Tajikistan','Tanzania','Thailand','Togo','Tokelau','Tonga','Trinidad','Tobago','Tunisia','Turkey','Turkmenistan','Tuvalu','Uganda','Ukraine','Britain','England','Scotland','Wales','America','Uruguay','Uzbekistan','Vanuatu','Vatican','Venezuela','Vietnam','Wallis','Futuna','Sahara','Yemen','Yugoslavia','Zambia','Zimbabwe']

import random

class Mdict:
    def __init__(self):
        self.d = {}
    def __getitem__(self, key):
        if key in self.d:
            return self.d[key]
        else:
            raise KeyError(key)
    def add_key(self, prefix, suffix):
        if prefix in self.d:
            self.d[prefix].append(suffix)
        else:
            self.d[prefix] = [suffix]
    def get_suffix(self,prefix):
        l = self[prefix]
        return random.choice(l)

class MName:
    # A name from a Markov chain
    def __init__(self, chainlen = 2):
        # Building the dictionary
        if chainlen > 10 or chainlen < 1:
            print "Chain length must be between 1 and 10, inclusive"
            sys.exit(0)

        self.mcd = Mdict()
        oldnames = []
        self.chainlen = chainlen

        for l in PLACES:
            l = l.strip()
            oldnames.append(l)
            s = " " * chainlen + l
            for n in range(0,len(l)):
                self.mcd.add_key(s[n:n+chainlen], s[n+chainlen])
            self.mcd.add_key(s[len(l):len(l)+chainlen], "\n")

    def New(self):
        # New name from the Markov chain
        prefix = " " * self.chainlen
        name = ""
        suffix = ""
        while True:
            suffix = self.mcd.get_suffix(prefix)
            if suffix == "\n" or len(name) > 9:
                break
            else:
                name = name + suffix
                prefix = prefix[1:] + suffix
        return name.capitalize()

for i in range(100):
    print MName().New()