def next(s):
    n = len(s)
    if n == 0:
        return False
    i = n - 1
    while i >= 0:
        if s[i] < 9:
            s[i] += 1
            return True
        else:
            s[i] = 0
            i -= 1
    return False
    
def isLucky(s):
    n = len(s)
    if n == 0:
        return True
    k = n // 2
    s0 = 0
    for i in range(k):
        s0 += s[i]
    s1 = 0
    for i in range(k, n):
        s1 += s[i]
    return s0 == s1    

def luckyTickets(n):
    s = [0]*n
    tickets = []
    while True:
        if isLucky(s):
            tickets.append(s.copy())
        if not next(s):
            break        
    return tickets    
        
def numLuckyTickets(n):
    s = [0]*n
    num = 0
    while True:
        if isLucky(s):
            num += 1
        if not next(s):
            break        
    return num    
    
def main():
    print("List of lucky tickets of length n")
    while True:
        try:
            n = int(input("Enter n <= 6 or 'q' for quit: "))
            if n <= 0:
                break
            elif n > 6:
                print("n is too large...")
                continue
            elif n%2 != 0:
                print("n must be even.")
                continue
        except ValueError:
            break

        tickets = luckyTickets(n)
        # print(tickets)
        for t in tickets:
            print(t)
        print("Number of lucky tickets =", len(tickets))

if __name__ == "__main__":
    main()