Given an array A, we can do the following operation as many times as needed: choose (i, j) such that ...

---

Given an array A, we can do the following operation as many times as needed: choose (i, j) such that 1 <= i < j <= |A| and A_i = A_j, then delete both values from the array and append 2 * A_i at the end of the array. For example, if A = [3, 1, 3, 4, 4] and we choose (i, j) = (1, 3), the new array is [1, 4, 4, 6]. Let f(A) denote the minimum possible size of the array A after doing these operations. Given an array A of size N, solve for all prefixes of the array: find f(A[1,1]), f(A[1,2]), f(A[1,3]), ..., f(A[1,N]), where A[L,R] denotes the array [A_L, A_(L+1), ..., A_R]. Constraints: T test cases with 1 <= T <= 10^4; 1 <= N <= 2*10^5; 1 <= A_i <= 10^9; the sum of N over all test cases does not exceed 2*10^5. Input: T, then for each test case N followed by the N integers of A. Output: for each test case, one line with the values f(A[1,1]), ..., f(A[1,N]).