Sưởi ấm

Ngôi nhà của bạn có $n$ phòng. Ở phòng thứ $i$ bạn có thể lắp tối đa $c_i$ lò sưởi. Mỗi lò sưởi có thể gồm nhiều đốt (section), và một lò sưởi có $k$ đốt có chi phí là $k^2$.

Do các phòng có kích thước khác nhau, phòng thứ $i$ cần tổng cộng ít nhất $su{m}_i$ đốt.

Với mỗi phòng, hãy tính chi phí nhỏ nhất để lắp không quá $c_i$ lò sưởi sao cho tổng số đốt không nhỏ hơn $su{m}_i$.

Dữ liệu vào

• Dòng đầu chứa một số nguyên $n$: số phòng.
• $n$ dòng tiếp theo, dòng thứ $i$ chứa hai số nguyên $c_i$ và $su{m}_i$: số lò sưởi tối đa và tổng số đốt tối thiểu của phòng thứ $i$.

Dữ liệu ra

Với mỗi phòng, in ra một số nguyên trên một dòng: chi phí nhỏ nhất.

Ràng buộc

• $1\le n\le 1000$
• $1\le c_i,su{m}_i\le {10}^4$

Ví dụ