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