// Задача "Возведение в степень"
// 1-ая личная интернет-олимпиада сезона 2009-2010
// Автор задачи: Владимир Ульянцев, ulyantsev@rain.ifmo.ru
// Автор решения: Владимир Ульянцев, ulyantsev@rain.ifmo.ru

// Генератор правильного решения

type
    int = longint;
const
    MAXK = 17;
    C = 64;
var
    k, b, a : int;
    ans, l, r : int64;

function pow(n, k : int) : int64;
begin
    result := 1;
    while (k > 0) do begin
        result := result * n;
        k := k - 1;
    end;
end;

begin
    rewrite(output, 'pow_vu.dpr');

    writeln('// generated with generate_vu_precalc.dpr');
    writeln('var');
    writeln('   k : integer;');
    writeln('   a : array [1..17] of int64;');
    writeln('begin');
    

    for k := 1 to MAXK do begin
        l := pow(10, k - 1);
        r := pow(10, k);

        ans := r - l;

        if (k = 1) then
            ans := ans - 1;

        for b := 2 to C do begin
            a := 2;

            while (pow(a, b) < r) do begin
                if (pow(a, b) >= l) then begin
                    ans := ans + 1;
                end;
                a := a + 1;
            end;      
        end;

        writeln('   a[', k, '] := int64(', ans, ');')
    end;

    writeln('');
    writeln('   reset(input, ''pow.in'');');
    writeln('   rewrite(output, ''pow.out'');');
    writeln('   read(k);');
    writeln('   writeln(a[k]);');
    writeln('end.');
end.
