Ним -- это игра для двух игроков, которые по очереди берут предметы, разложенные на несколько кучек. Каждый игрок в свой ход может выбрать одну из непустых кучек и забирать из нее любое ненулевое количество предметов. Проигрывает тот из игроков, кто в свою очередь не сможет сделать ход (то есть последний предмет заберет на предыдущем ходе его соперник). Данная игра математически полностью проанализирована. Проигрышными позициями в игре называются такие позиции, что при любых дальнейших ходах игрока, который должен делать ход из данной позиции, его соперник имеет возможность делать такие ходы, которые приведут к проигрышу игрока (то есть соперник имеет выигрышную стратегию). Выигрышными -- такие, что, каковы бы ни были в дальнейшем действия соперника, игрок, который выполняет ход из данной позиции, имеет возможность делать такие ходы, которые приведут его к победе (то есть игрок имеет выигрышную стратегию). Известно, что выигрышность позиции определяется ним-суммой: \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 Выведите единственное целое число -- количество вариантов первого хода, которое допускает выигрышная стратегия.