Problema A - Regras Quadriculadas

Como sabes desde a qualificação, a Sara adora o seu caderno quadriculado e arranja todo o tipo de maneiras de passar tempo com ele. Desta vez resolveu começar a pintar com o seu lápis algumas quadrículas. A partir da maneira como preenche uma linha do caderno, ela faz as seguintes transformações a cada quadrícula:

A Sara começa por pintar na primeira linha apenas uma quadrícula. A partir daí pinta nas linhas sucessivas usando as regras indicadas. A figura seguinte ilustra a maneira como ficariam as 3 primeiras linhas do caderno:

A Sara achou que o caderno estava a ficar com um padrão muito bonito! Como adora contar, resolveu selecionar uma parte de uma das linhas e contar quantas quadrículas estão pintadas. Por exemplo, entre a 3ª e a 7ª posição da 3ª linha existem duas quadrículas pintadas:

A Sara rapidamente percebeu que ia dar muito trabalho contar quadrículas para as linhas seguintes e precisa da tua ajuda!

O Problema

Sabendo que a Sara usa as regras atrás descritas começando com uma única quadrícula pintada na primeira linha, a tua tarefa é responder a vários pedidos de contagens, cada um deles no seguinte formato: na linha nº K_i, quantas quadrículas estão pintadas entre as posições A_i e B_i (inclusive)?

Input

Na primeira linha vem um único inteiro P indicando o número de perguntas que se seguem. Cada uma das P linhas seguintes contém três inteiros K_i A_i B_i indicando o intervalo [A_i,B_i] da linha nº K_i. É garantido que as posições são válidas para a linha em questão, ou seja, não saem dos seus limites.

Output

O output deve conter P linhas, uma para cada pergunta, indicando o número de quadrículas pintadas entre as posições A_i e B_i da K_i-ésima linha do caderno

Restrições

São garantidos os seguintes limites em todos os casos de teste que irão ser colocados ao programa:

Nota que para ler um número da ordem de 10¹⁶ são necessários 64 bits, ou seja, deves usar o long long de C/C++ ou o long de Java.

Os casos de teste deste problema estão organizados em 5 grupos com restrições adicionais diferentes:

Exemplo de Input

5
3 3 7
3 1 8
2 1 1
5 27 41
4 9 12

Exemplo de Output

2
4
1
5
0

Explicação do Exemplo

A seguir são mostrados os segmentos correspondentes a cada uma das perguntas:

• 3 3 7: posições 3 a 7 da 3ª linha (2 quadrículas pintadas)

• 3 1 8: posições 1 a 8 da 3ª linha (4 quadrículas pintadas)

• 2 1 1: posições 1 a 1 da 2ª linha (1 quadrícula pintada)

• 5 27 41: posições 27 a 41 da 5ª linha (5 quadrículas pintadas)

• 4 9 12: posições 9 a 12 da 4ª linha (0 quadrículas pintadas)