Непустая строка s называется бинарной, если она состоит только из символов «0» и «1». Пронумеруем символы бинарной строки s от 1 до длины строки и обозначим i-й символ строки s как si.
Бинарную строку s длины n будем называть периодической, если существует целое число 1 ≤ k < n такое, что:
- k — делитель числа n
- для всех 1 ≤ i ≤ n - k выполняется si = si + k
Например, бинарные строки «101010» и «11» являются периодическими, а «10» и «10010» — нет.
Целое положительное число x будем называть периодическим, если бинарная строка, являющаяся записью числа x в двоичной системе счисления (без лидирующих нулей), — периодическая.
Ваша задача — найти количество периодических чисел в отрезке от l до r (оба конца включены).
Выходные данные
Выведите единственное целое число — количество периодических чисел в отрезке от l до r (оба конца включены).
Примечание
В первом примере периодическими числами являются 3, 7 и 10.
Во втором примере периодическими числами являются 31 и 36.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1 10
|
3
|
|
2
|
25 38
|
2
|