В ходе проведения очередной весенней уборки, Даниэль нашел старый калькулятор, который ему очень понравился. Однако кажется, что что-то в нем сломано. Когда он хочет посчитать \(1 + 3\) c помощью калькулятора, он получает \(2\) вместо \(4\). Но при вычислении \(1 + 4\) ответ получается правильный, \(5\). Озадаченный таким поведением, он вскрыл калькулятор и нашел разгадку: полные сумматоры стали полусумматорами!
Теперь, когда он хочет посчитать \(a + b\) при помощи калькулатора, он получает ксор-сумму \(a \oplus b\) (определение можно прочитать по ссылке: https://ru.wikipedia.org/wiki/Сложение_по_модулю_2).
Но как он уже заметил ранее, калькулятор иногда выдает правильные ответы. Поэтому его интересует, при данных \(l\) и \(r\) сколько существует таких пар целых чисел \((a, b)\), для которых выполняются следующие условия: \(\)a + b = a \oplus b\(\) \(\)l \leq a \leq r\(\) \(\)l \leq b \leq r\(\)
Даниэль Бармен, однако, сейчас направляется в бар, а вернется только через пару часов. Он советует вам решить эту задачу до его возвращения, или же вы будете забанены.
Примечание
\(a \oplus b\) обозначает побитовое исключающее ИЛИ \(a\) и \(b\).
В первом примере подходящие пары: \((1, 2)\), \((1, 4)\), \((2, 1)\), \((2, 4)\), \((3, 4)\), \((4, 1)\), \((4, 2)\), и \((4, 3)\).