Ta xét hoán vị ~a~ của ~n~ phần tử ~1, 2, ..., n~.
Một dãy con của ~a~ là dãy thu được nếu xóa đi một số phần tử (có thể không xóa) từ ~a~ và giữ nguyên thứ tự các phần tử còn lại. Ví dụ: ~\{1, 3, 4\}~ là dãy con của ~\{1, 2, 3, 4, 5\}~, còn ~\{2, 1\}~ và ~\{1, 5, 2\}~ thì không.
Khi đó, ta định nghĩa ~LIS(a)~ là độ dài dãy con tăng dần dài nhất của dãy ~a~; tương tự với ~LDS(a)~ là độ dài dãy con giảm dần dài nhất của ~a~.
Gọi ~g(n) = min\{max\{LIS(a), LDS(a)\}\}~ với mọi hoán vị ~a~ độ dài ~n~.
Yêu cầu: Cho ~q~ truy vấn dạng ~l~ ~r~. Với mỗi truy vấn bạn hãy tính ~g(l)+g(l+1)+...+g(r)~.
Input
Dòng đầu chứa số nguyên dương ~q~ ~(q \le 10^5)~.
~q~ dòng tiếp, mỗi dòng chứa hai số nguyên ~l,r~ ~(1\le l \le r \le 10^9)~.
Output
In ra ~q~ dòng, mỗi dòng là đáp án cho truy vấn tương ứng.
Subtask
Có ~25\%~ số test của bài với ~q,r \le 1000~.
Có ~25\%~ số test khác của bài với ~1\le l \le r \le 10^6~ trong mọi truy vấn.
Có ~25\%~ số test khác với ~q=1~.
Còn lại không có điều kiện gì thêm.
Sample Input
5
1 2
3 5
30 50
150 200
1 1000000000
Sample Output
3
7
141
698
21082351068005
Note
Các dãy có ~max\{LCS, LDS\}~ là nhỏ nhất trong một số trường hợp:
~n = 1~: ~[1]~
~n = 2~: ~[2, 1]~
~n = 3~: ~[1, 3, 2]~
~n = 4~: ~[2, 4, 1, 3]~
~n = 5~: ~[5, 2, 4, 1, 3]~
Bình luận