E. 宇宙射线

• 每个测试的时间限制：2 秒
• 每个测试的内存限制：512 兆字节

---

给定一个整数数组 $s_1, s_2, \dots, s_l$。
每一秒，宇宙射线会导致所有满足 $i=1$ 或 $s_i \neq s_{i-1}$ 的 $s_i$ 被同时删除，然后将剩下的部分按原顺序拼接起来，形成新的数组 $s_1, s_2, \dots, s_{l'}$。

定义数组的 强度（strength） 为它变为空数组所需的秒数。

---

现在，你得到的数组是以压缩形式给出的：$n$ 个二元组从左到右描述整个数组。
每个二元组 $(a_i, b_i)$ 表示连续 $a_i$ 个 $b_i$，即：

[ \underbrace{b_i, b_i, \dots, b_i}_{a_i \text{ 次}} ]

对于每个 $i = 1, 2, \dots, n$，请找出由前 $i$ 个二元组所描述的序列的强度。

---

输入格式

每个测试点包含多个测试用例。
第一行一个整数 $t$（$1 \le t \le 10^4$）——测试用例的数量。

每个测试用例的第一行是一个整数 $n$（$1 \le n \le 3 \cdot 10^5$）——二元组的数量。

接下来的 $n$ 行，每行两个整数 $a_i, b_i$（$1 \le a_i \le 10^9, \ 0 \le b_i \le n$），描述该二元组。

保证对于所有 $1 \le i < n$，$b_i \neq b_{i+1}$。

保证所有测试用例的 $n$ 之和不超过 $3 \cdot 10^5$。

---

输出格式

对于每个测试用例，输出一行 $n$ 个整数，表示每个前缀的答案。

---

示例

输入：

4
4
2 0
1 1
3 0
5 1
6
4 6
1 3
4 6
4 0
7 6
6 3
7
9 0
7 1
5 0
7 1
9 0
1 1
2 0
10
10 7
4 9
2 2
7 9
2 8
8 5
11 7
15 5
12 7
4 0

输出：

2 2 4 5 
4 4 7 7 10 10 
9 9 9 9 9 9 10 
10 10 10 10 10 10 12 15 15 15 

---

样例解释

第一个测试用例，对于前 4 个二元组（即完整的前缀）：
数组为：

[ [0,0,1,0,0,0,1,1,1,1,1] ]

变化过程：

1. $[0,0,1,0,0,0,1,1,1,1,1] \to [0,0,0,1,1,1,1]$
2. $\to [0,0,1,1,1]$
3. $\to [0,1,1]$
4. $\to [1]$
5. $\to []$

所以强度为 $5$。

---

第二个测试用例，对于前 4 个二元组：
数组为：

[ [6,6,6,6,3,6,6,6,6,0,0,0,0] ]

变化过程：

1. $\to [6,6,6,6,6,6,0,0,0]$
2. $\to [6,6,6,6,6,0,0]$
3. $\to [6,6,6,6,0]$
4. $\to [6,6,6]$
5. $\to [6,6]$
6. $\to [6]$
7. $\to []$

强度为 $7$。