#include <stdlib.h>
#include <stdio.h>

int** N;

void prepare()
{
    int i;
    N = malloc(9 * sizeof(int*));
    for (i = 1; i <= 8; i++)
    {
        int length = i * 9 + 1;
        N[i] = malloc(length * sizeof(int));

        if (i == 1)
        {
            int j;
            for (j = 0; j < length; j++)
                N[i][j] = 1;
        }
        else
        {
            int runningsum = 0;
            int k = 0;
            for ( ; k <= length / 2; k++)
            {
                runningsum += N[i-1][k];
                if (k >= 10)
                   runningsum -= N[i-1][k-10];
                N[i][k] = runningsum;
            }
            for ( ; k < length; k++)
            {
                N[i][k] = N[i][length - 1 - k];
            }
        }
    }
}

static unsigned long long l_t(size_t digits)
{
    unsigned long long tickets = 0;
    size_t i = 0;

    for( ; i <= (digits*9); i++ )
    {
        unsigned long long n = N[digits][i];
        tickets += n*n;
    }
    return tickets;
}

int main()
{
    prepare();
    printf
    (
        "1: %llu\n2: %llu\n3: %llu\n4: %llu\n5: %llu\n6: %llu\n7: %llu\n8: %llu\n", 
        l_t(1),l_t(2),l_t(3),l_t(4),l_t(5),l_t(6),l_t(7),l_t(8)
    );
    return 0;
}