Đề bài

Cho hai số nguyên dương ~a, b~.

Yêu cầu: Hãy tính ~S(a, b) = a^3 + (a + 1)^3 + \dots + b^3~.

Input

• Dòng đầu chứa số nguyên dương ~T~ - số lượng testcase (~T \leq 10^4~).
• ~T~ dòng tiếp theo, mỗi dòng là hai số nguyên dương ~a, b~ (~a \leq b \leq 10^6~).

Output

Gồm ~T~ dòng, với mỗi dòng in ra ~S(a, b)~ tương ứng.

Ví dụ

Sample Input

2
1 3
4 6

Sample Output

36
405

Giới hạn

• 40% số điểm có ~T \leq 10^3~ và ~a, b \leq 100~.
• 60% số điểm còn lại không giới hạn gì thêm.