B. Antigo
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
Eu nu strivesc corola de minuni a lumii

şi nu ucid

cu mintea tainele, ce le-ntâlnesc

în calea mea

în flori, în ochi, pe buze ori morminte.

Lumina altora

sugrumă vraja nepătrunsului ascuns

în adâncimi de întuneric,

dar eu,

eu cu lumina mea sporesc a lumii taină -

şi-ntocmai cum cu razele ei albe luna

nu micşorează, ci tremurătoare

măreşte şi mai tare taina nopţii,

aşa îmbogăţesc şi eu întunecata zare

cu largi fiori de sfânt mister

şi tot ce-i neînţeles

se schimbă-n neînţelesuri şi mai mari

sub ochii mei-

căci eu iubesc

şi flori şi ochi şi buze şi morminte.

— Lucian Blaga, Eu nu strivesc corola de minuni a lumii

Recently, the International Olympiad in Antigo has been announce to be held this year, and Aznurf has begun training for it. Antigo is a game similar to Go, only that it is played on a finite rectangular surface on an infinite table. For simplicity, the entire table is an xOy cartezian plane, and before each round, the players are announced that they will play with the points in the rectangular area between lower-left corner $$$(x1,y1)$$$ and upper-right $$$(x2,y2)$$$ (i.e. any point defined by $$$(x,y)$$$ such that $$$x1 \le x \le x2$$$ and $$$y1 \le y \le y2$$$ will be considered inside the area). With few fays before the championship, Aznurf found the key to the perfect opening move: any point defined by $$$(A,B)$$$ is given a value, which is either 1 if the point is "valorous" or 0 otherwise. If F(A,B) is the value of this point, then:

$$$F(A,B) = \left\{ \begin{array}{ c l } 1 & \quad \textrm{if } A=0 \textrm{ and } B=0 \\ F(A/5,B/5) & \quad \textrm{if } (A \textrm{ mod } 5) \textrm{ mod } 3 = (B \textrm{ mod } 5) \textrm{ mod } 3 \\ 0 & \quad \textrm{otherwise} \end{array} \right.$$$

One can reconsider this process as if both numbers are first converted to base 5, then after putting one above the other, each pair of corresponding digits are congruent modulo 3. Such an example of a point with value 1 would be (11206,1399), because $$$11206=324311_{(5)}, 1399=021044_{(5)}$$$ and $$$3 \equiv 0, 2 \equiv 2, 4 \equiv 1, 3 \equiv 0, 1 \equiv 4, 1 \equiv 4$$$

An hour before the contest, Aznurf gave into pressure saying "I want to start playing some game that is at least respected, like chess" , so now you're the only one in the national team.

After the competition, you made a fool of yourself. You're now curios in how many ways for each game in how many ways you could've opened the game, respecting the rules of Aznurf.

Input

On the first line you have Q, the number of areas you have. Then, on each of the following Q lines, you are given $$$x1_{i},y1_{i},x2_{i},y2_{i}$$$, representing the i-th query

Output

For each query, print the sum of the values of the points inside the respective rectangle

Scoring

Restrictions:

$$$1\le Q \le 1\,000$$$

$$$1 \le x1 \le x2 \le 10^{18}$$$

$$$1 \le y1 \le y2 \le 10^{18}$$$

Additionally:

  • For 20 points (group 1), the area in the rectangles given at input does not surpass $$$55\,000\,000$$$
  • For another 40 points (group 2), the perimeter in the rectangles given at input does not surpass $$$200\,000$$$
Example
Input
3
1 1 5 5
1 3 4 6
365 100 425 178
Output
7
3
81
Note

For the first game, we have the points with value 1: $$$(1,1), (2,2), (3,3), (4,4), (5,5), (1,4)$$$ and $$$(4,1)$$$

For the second game, we have the points with value 1: $$$(3,3), (4,4)$$$ and $$$(1,4)$$$

For the third game, we have a lot of points with value 1, so we ask you to believe us.