신욱이는 $10^9 \times 10^9$ 크기의 커다란 격자판을 가지고 재밌는 놀이를 하고 있다.</p>

신욱이는 처음에 색이 칠해져 있지 않은 격자판으로 놀이를 시작하며, 다음과 같은 행동을 $Q$회 반복한다.

• $1$ 이상 $10^9$ 이하의 정수 $x, y$를 고른다.
• $1 \le i \le x, 1 \le j \le y$ 를 만족하는 모든 격자점 $(i, j)$ 를 검게 칠한다. 이 과정에서 이미 검게 칠해진 격자점에 덧칠하더라도 색이 변하지 않는다.
• 현재 검게 칠해진 격자점의 수를 외친다.

신욱이가 $Q$회에 걸쳐 고른 정수 $x, y$가 주어질 때, $Q$회에 걸쳐 외친 수가 각각 무엇이었는지 알아내 보자.

입력 형식

첫째 줄에 정수 $Q$가 주어진다. $(1 \le Q \le 300\,000)$</p>

둘째 줄부터 $Q$개의 줄에 걸쳐 정수 $x_i, y_i$가 공백으로 구분되어 주어진다. $(1 \le x_i,y_i \le 10^9)$

$x_i$와 $y_i$는 각각 신욱이가 $i$번째에 고른 정수 $x$와 $y$를 나타낸다.

출력 형식

신욱이가 외친 수들을 순서대로 $Q$개의 줄에 걸쳐 출력한다.

예제 입력 1

5
1 5
2 4
3 3
4 2
5 1

예제 출력 1

5
9
12
14
15

예제 입력 2

5
1 5
2 6
3 7
4 8
5 9

예제 출력 2

5
12
21
32
45

예제 입력 3

5
5 1
4 2
3 3
2 2
1 1

예제 출력 3

5
9
12
12
12

예제 입력 4

1
1000000000 1000000000

예제 출력 4

1000000000000000000