Cho dãy số sau: 1 3 5 7 9 11 13... Các số được đánh thứ tự bắt đầu từ 1.

Yêu cầu: Hãy tính tổng các số hạng từ số thứ x đến số thứ y trong dãy trên.

Dữ liệu vào:

• Dòng 1. Số nguyên dương N - Là số bộ test(~1 \le N \le 10^6~)
• N dòng tiếp theo mỗi dòng ghi 2 số nguyên dương ~x~, ~y~ (~1 \le x \le y \le 10^9~).

Dữ liệu ra:

• Gồm N dòng, mỗi dòng ghi 1 số nguyên k là tổng các phần tử từ x đến y ứng với N bộ test đã cho.

Ví dụ:

Input

2
2 5
1 3

Output

24
9