infinit

Разглеждаме редица, образувана по следния начин:
-
първоначално, редицата е "1";
-
последователно на стъпки се извършва следната трансформация с редицата: "1" -> "10" и "0" -> "1".
След безброй много стъпки получаваме редицата "
1011010110110101101...".
Задават се Q въпроса от вида: колко знака 1 са в редицата между позициите с номера a и b ?

Задача

Напишете програма, която дава отговорите на Q-те въпроса.

Вход

Първият ред на входния файл infinit.in съдържа числото Q. Всеки от следващите Q реда съдържа двойка от числа a, b, разделени с интервал.

Изход

Файлът infinit.out трябва да се състои от Q реда, като i–тият съдържа отговора за двойката  (a, b) от (i+1)-ия ред на входния файл.

Ограничения

Пример

infinit.in

infinit.out

1
2 8

4

Time limit: 0.1 секунди за тест

Tiberiu-Lucian Florea
University of Bucharest, Mathematics & IT Department
Contact: tiberiu.florea@gmail.com

Български превод: Емил Келеведжиев