Sau khi đánh bại Mabư Béo, nhiệm vụ tiếp theo của Piccôlô chính là ở lại quê nhà, xây dựng một Võ đài để cho các đấu sĩ trẻ có thể luyện tập một cách hiệu quả hơn.

Vùng đất của Đại Ma Vương Piccôlô có thể được thể hiện bằng hệ trục tọa độ ~Oxy~. Võ đài mà Piccôlô xây nên sẽ là một hình chữ nhật, mà các điểm góc của nó đều có tọa độ nguyên.

Ở trong võ đài, ta sẽ xây một số "Trạm Mana" để tiếp sức cho các đấu sĩ, cũng như cho phép họ sử dụng các chiêu thức sáng tạo, tận dụng những trạm này để giành lấy lợi thế cho bản thân. Tuy nhiên, Trạm Mana sẽ chỉ có thể đặt được ở các vị trí có tọa độ nguyên dương ~(x, y)~ mà thỏa mãn tính chất đặc biệt: ~x * y~ là một số nửa nguyên tố.

Ta định nghĩa số nửa nguyên tố là tích của hai số nguyên tố khác nhau. Chẳng hạn: ~6, 10, 21~ là những số nửa nguyên tố, nhưng ~1, 3, 30, 9~ thì không phải.

Piccôlô nhận được ~N~ đề xuất cho các vị trí khác nhau để xây dựng võ đài. Mỗi đề xuất có dạng ~a, b, c, d~, thể hiện rằng võ đài đặt ở vị trí hình chữ nhật, có góc trái dưới ở điểm ~(a, b)~, và góc phải trên đặt ở đỉnh ~(c, d)~. Nhiệm vụ của bạn: với mỗi đề xuất, hãy tính số điểm có thể đặt Trạm Mana trên Võ đài.

Trạm Mana có thể được đặt ở cả điểm góc, lẫn điểm nằm trên cạnh của hình chữ nhật.

Input

Dòng đầu chứa ~N~ (~1 \le N \le 10^5~) - số đề xuất Piccôlô nhận được.

~N~ dòng sau, mỗi dòng chứa bốn số: ~a, b, c, d~ (~1 \le a \le c \le 10^6~, ~1 \le b \le d \le 10^6~), thể hiện giới hạn của hình chữ nhật trong mỗi đề xuất.

Output

Với mỗi đề xuất, in ra trên một dòng một số nguyên duy nhất, ứng với số điểm bạn tìm được.

Sample Input 1

5
2 2 7 5
1 3 2 8
1 1 1000 1000
1 1 1000000 1000000
99999 99999 1000000 1000000

Sample Output 1

9
4
28632
6162277240
4747967930

Notes

Đối với hình chữ nhật thứ nhất trong bộ test, ~9~ điểm được đánh dấu dưới đây là những điểm thỏa mãn:

Đối với hình chữ nhật thứ hai trong bộ test, ~4~ điểm được đánh dấu dưới đây là những điểm thỏa mãn: