СуперНім Junior
Нім – це гра для двох гравців, які по черзі беруть предмети, розкладені на декілька купок. Кожен гравець своїм ходом може вибрати одну з непорожніх купок і забрати з неї довільну ненульову кількість предметів. Програє той з гравців, хто у свою чергу не зможе зробити хід (тобто останній предмет забере на попередному ході його супротивик).
Дана гра математично повністю проаналізована. Програшними позиціями у грі називаються такі позиції, що при довільних подальших ходах гравця, який повинен робити хід з даної позиції, його суперник має можливість робити такі ходи, які призведуть до програшу гравця (тобто суперник має виграшну стратегію). Виграшними – такі, що, якмим б не були у подальшому дії суперника, гравець, який виконує хід з даної позиції, має можливість робити такі ходи, які призведуть його до перемоги (тобто гравець має виграшну стратегію). Віжомо, що виграшність позиції визначається нім-сумою: p_1 xor p_2 xor ... xor p_N, де p_i – кількість предметів у i-ій купці, xor – операція побітового виключного "або" (додавання двійкових подань чисел без врахування переносів у наступні розряди). Якщо ця сума відмінна від нуля, то позиція виграшна, якщо дорівнює нулю – програшна.
Туть ми будемо мати справу з величезною кількістю купок. Ваше завдання – за заданими розмірами купок визначити кількість виграшних варіантів першого ходу першого гравця з початкової позиції (тобто такі ходи, при яких виграшна стратегія все ще буде залишатись у першого гравця).
Вхідні дані
У першому рядку вхідного файлу міститься ціле число M, яке визначає кількість груп купок. Кожен з натупних M рядків описує відповідну групу при допомозі двох цілих чисел a, b. У групі буде b-a+1 купок з розмірами від a до b включно.
1 ≤ M ≤ 100000, 0 ≤ a ≤ b ≤ 10^12.
Вихідні дані
Виведіть єдине ціле число – кількість варіантів першого хода, які допускає виграшна стратегія.