Given an array of integers (s_1, s_2, \ldots, s_l), every second, cosmic rays will cause all (s_i) such that (i=1) or (s_i\neq s_{i-1}) to be deleted simultaneously, and the remaining parts will be concatenated together in order to form the new array (s_1, s_2, \ldots, s_{l'}). Define the strength of an array as the number of seconds it takes to become empty. You are given an array of integers compressed in the form of (n) pairs that describe the array left to right. Each pair ((a_i,b_i)) represents (a_i) copies of (b_i), i.e. (\underbrace{b_i,b_i,\cdots,b_i}_{a_i\textrm{ times}}). For each (i=1,2,\dots,n), please find the strength of the sequence described by the first (i) pairs. Each test contains multiple test cases. The first line contains the number of test cases (t) ((1\le t\le10^4)). The description of the test cases follows. The first line of each test case contains a single integer (n) ((1\le n\le3\cdot10^5)) — the length of sequence (a). The next (n) lines contain two integers each (a_i), (b_i) ((1\le a_i\le10^9,0\le b_i\le n)) — the pairs which describe the sequence. It is guaranteed that the sum of all (n) does not exceed (3\cdot10^5). It is guaranteed that for all (1\le i<n), (b_i\neq b_{i+1}) holds. For each test case, print one line containing (n) integers — the answer for each prefix of pairs. In the first test case, for the prefix of length (4), the changes will be (0,0,1,0,0,0,1,1,1,1,1\rightarrow0,0,0,1,1,1,1\rightarrow0,0,1,1,1\rightarrow0,1,1\rightarrow1\rightarrow[]), so the array becomes empty after (5) seconds. In the second test case, for the prefix of length (4), the changes will be (6,6,6,6,3,6,6,6,6,0,0,0,0\rightarrow6,6,6,6,6,6,0,0,0\rightarrow6,6,6,6,6,0,0\rightarrow6,6,6,6,0\rightarrow6,6,6\rightarrow6,6\rightarrow6\rightarrow[]), so the array becomes empty after (7) seconds.