PASCAL
В свободное время R2-D2 и C3-PO, чтобы их платы совсем не заржавели, любят задавать друг другу задачи. Последняя задача, которую R2-D2 задал C3-PO, называется "подходящие числа". Он считает подходящим десятичное число, двоичная запись которого заканчивается не менее чем X нулями. Помогите C3-PO узнать, сколько таких чисел существует в диапазоне от M до N включительно.


Формат ввода

На вход через пробел подаётся три натуральных числа M, N, X (1 ≤ M ≤ N ≤ 1 000 000 000, 0≤ X ≤ 20).


Формат вывода

Вывести одно целое число – количество целых чисел, удовлетворяющих условию.


Пример

Ввод Вывод

2 30 3

3

Ответ:

program DecToBinCount;

uses

 SysUtils, StrUtils;

function DecToBin (m: Integer): string;

var

 r: Integer;

 s: string;

begin

 while (m > 0) do Begin

  r := m mod 2;

  m := m div 2;

  s := IntToStr (r) + s;

 end;

 Result := s;

end;

var

 m, n, x, i, c: Integer;

 s: string;

begin

 Write ('Введите M, N, X: ');

 ReadLn (m, n, x);

 WriteLn;

 c := 0;

 for i := m to n do begin

   s := DecToBin (i);

   if RightStr (s, x) = StringOfChar ('0', x) then begin

     WriteLn (s, ' ');  // для проверки. после тестирования закомментарить

     Inc (c);

   end;

 end;

 WriteLn (c);

 ReadLn;

end.