Виталий известный в школе пиротехник. Не один раз уже из-за него приходилось менять окна, ставить на место двери и ремонтировать компьютеры. Но наконец-то выпуск и Виталий может полностью раскрыть свои таланты, подготувив самый грандизный феерверк за всю историю своей школы. Для этого ему нужны 2 вещества. Но не всё так просто: чтобы феерверк был красивым и мощным, нужно, чтобы сила взрыва была максимальной.
Сила взрыва расчитывается по формуле a XOR (a + 1) XOR ... XOR (b - 1) XOR b,
где a и b - количество первого и второго вещества соответственно, XOR - операция "исключающего ИЛИ" или "сложение по модулю 2". Виталий экспериментирует с количествами веществ, а ваша задача - находить силу взрыва для каждого его запроса.
В первой строке задано количество запросов t (1 ≤ t ≤ 50000). В последующих t строках заданы сами запросы: числа a[i]
и b[i]
- количества двух веществ (0 ≤ a[i]
≤ b[i]
≤ 2^31
- 1).
Для каждого запроса в отдельной строке выведите силу взрыва.