# your code goes here
class Solution(object):
    def findStrobogrammatic(self, n):
        even_mid_candidates = ["11","69","88","96", "00"]
        odd_mid_candidates = ["0", "1", "8"]
        if n == 1:
            return odd_mid_candidates
        if n == 2:
            return even_mid_candidates[:-1]
        if n % 2:
            pre_candidates, mid_candidates = self.findStrobogrammatic(n-1), odd_mid_candidates
        else: 
            pre_candidates, mid_candidates = self.findStrobogrammatic(n-2), even_mid_candidates
        pre_mid_pos = (n-1)/2
        result = []
        for c in mid_candidates:
            for p in pre_candidates:
                result.append(p[:pre_mid_pos] + c + p[pre_mid_pos:])
        return result 

IyB5b3VyIGNvZGUgZ29lcyBoZXJlCmNsYXNzIFNvbHV0aW9uKG9iamVjdCk6CiAgICBkZWYgZmluZFN0cm9ib2dyYW1tYXRpYyhzZWxmLCBuKToKICAgICAgICBldmVuX21pZF9jYW5kaWRhdGVzID0gWyIxMSIsIjY5IiwiODgiLCI5NiIsICIwMCJdCiAgICAgICAgb2RkX21pZF9jYW5kaWRhdGVzID0gWyIwIiwgIjEiLCAiOCJdCiAgICAgICAgaWYgbiA9PSAxOgogICAgICAgICAgICByZXR1cm4gb2RkX21pZF9jYW5kaWRhdGVzCiAgICAgICAgaWYgbiA9PSAyOgogICAgICAgICAgICByZXR1cm4gZXZlbl9taWRfY2FuZGlkYXRlc1s6LTFdCiAgICAgICAgaWYgbiAlIDI6CiAgICAgICAgICAgIHByZV9jYW5kaWRhdGVzLCBtaWRfY2FuZGlkYXRlcyA9IHNlbGYuZmluZFN0cm9ib2dyYW1tYXRpYyhuLTEpLCBvZGRfbWlkX2NhbmRpZGF0ZXMKICAgICAgICBlbHNlOiAKICAgICAgICAgICAgcHJlX2NhbmRpZGF0ZXMsIG1pZF9jYW5kaWRhdGVzID0gc2VsZi5maW5kU3Ryb2JvZ3JhbW1hdGljKG4tMiksIGV2ZW5fbWlkX2NhbmRpZGF0ZXMKICAgICAgICBwcmVfbWlkX3BvcyA9IChuLTEpLzIKICAgICAgICByZXN1bHQgPSBbXQogICAgICAgIGZvciBjIGluIG1pZF9jYW5kaWRhdGVzOgogICAgICAgICAgICBmb3IgcCBpbiBwcmVfY2FuZGlkYXRlczoKICAgICAgICAgICAgICAgIHJlc3VsdC5hcHBlbmQocFs6cHJlX21pZF9wb3NdICsgYyArIHBbcHJlX21pZF9wb3M6XSkKICAgICAgICByZXR1cm4gcmVzdWx0IA==