Problem: Polycarp is an organizer of a Berland ICPC regional event. There are n universities in Berland numbered from 1 to n. Polycarp knows all competitive programmers in the region. There are n students: the i-th student is enrolled at a university u_i and has a programming skill s_i.

Polycarp has to decide on the rules now. In particular, the number of members in the team.

Polycarp knows that if he chooses the size of the team to be some integer k, each university will send their k strongest (with the highest programming skill s) students in the first team, the next k strongest students in the second team and so on. If there are fewer than k students left, then the team can't be formed. Note that there might be universities that send zero teams.

The strength of the region is the total skill of the members of all present teams. If there are no teams present, then the strength is 0.

Help Polycarp to find the strength of the region for each choice of k from 1 to n.

Input

The first line contains a single integer t (1 ≤ t ≤ 1000) — the number of testcases.

The first line of each testcase contains a single integer n (1 ≤ n ≤ 2 ⋅ 10^5) — the number of universities and the number of students.

The second line of each testcase contains n integers u_1, u_2, ..., u_n (1 ≤ u_i ≤ n) — the university the i-th student is enrolled at.

The third line of each testcase contains n integers s_1, s_2, ..., s_n (1 ≤ s_i ≤ 10^9) — the programming skill of the i-th student.

The sum of n over all testcases doesn't exceed 2 ⋅ 10^5.

Output

For each testcase print n integers: the strength of the region — the total skill of the members of the present teams — for each choice of team size k.

Example

Input


4
7
1 2 1 2 1 2 1
6 8 3 1 5 1 5
10
1 1 1 2 2 2 2 3 3 3
3435 3014 2241 2233 2893 2102 2286 2175 1961 2567
6
3 3 3 3 3 3
5 9 6 7 9 7
1
1
3083


Output


29 28 26 19 0 0 0 
24907 20705 22805 9514 0 0 0 0 0 0 
43 43 43 32 38 43 
3083 

Note

In the first testcase the teams from each university for each k are: 

  * k=1: 
    * university 1: [6], [5], [5], [3]; 
    * university 2: [8], [1], [1]; 
  * k=2: 
    * university 1: [6, 5], [5, 3]; 
    * university 2: [8, 1]; 
  * k=3: 
    * university 1: [6, 5, 5]; 
    * university 2: [8, 1, 1]; 
  * k=4: 
    * university 1: [6, 5, 5, 3]; 

Solution (in JAVA):

Solution:
// package contest;

import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.HashMap;
import java.util.InputMismatchException;
import java.util.Map;

public class C {
	private static PrintWriter out = new PrintWriter(System.out);

	public static void solve() {
		In in = new In();
		int tests = in.ni();
		while (tests-- > 0) {
			int n = in.ni();
			Integer[] us = in.nia(n);
			Integer[] ss = in.nia(n);

			long[] ans = new long[n + 1];

			int[] size = new int[n + 1];
			for (int u : us)
				size[u]++;
			
			Integer[][] skills = new Integer[n + 1][];
			for (int i = 1; i <= n; i++) {
				if (size[i] > 0) {
					skills[i] = new Integer[size[i]];
				}
			}
			int[] ps = new int[n + 1];
			for (int i = 0; i < us.length; i++) {
				skills[us[i]][ps[us[i]]++] = ss[i];
			}
			Map<Integer, BIT> bits = new HashMap<>();
			for (int i = 1; i < skills.length; i++) {
				if (skills[i] != null) {
					Arrays.sort(skills[i]);
					BIT bit = new BIT(skills[i].length);
					for (int j = 0; j < skills[i].length; j++)
						bit.update(j, skills[i][j]);
					bits.put(i, bit);
				}
			}
			for(int k = 1; k <= n && !bits.isEmpty(); k++) {
				long sum = 0;
				Map<Integer, BIT> nbits = new HashMap<>();
				for(Map.Entry<Integer, BIT> entry : bits.entrySet()) {
					Integer u = entry.getKey();
					BIT bit = entry.getValue();
					int take = k * (size[u] / k);
					sum += bit.sum(size[u] - take, size[u] - 1);
					if (k < size[u]) nbits.put(u, bit);
				}
				ans[k] = sum;
				bits = nbits;
			}
			for (int i = 1; i < ans.length; i++) {
				out.print(ans[i] + " ");
			}
			out.println();

		}
	}

	static class BIT {

		private final long[] vals; // array for which the prefix sum is evaluated
		private final long[] tree; // represents the BIT
		private final int size; // the size of the input array

		/**
		 * Instantiates a Binary Indexed Tree with an empty array.
		 * 
		 * @param n the number of elements
		 */
		public BIT(int n) {
			size = n;
			vals = new long[size];
			tree = new long[size + 1];
		}

		/**
		 * Instantiates a Binary Indexed Tree with an array.
		 * 
		 * @param n the number of elements
		 */
		public BIT(int[] nums) {
			size = nums.length;
			vals = new long[size];
			tree = new long[size + 1];
			for (int i = 0; i < size; i++)
				this.add(i, nums[i]);
		}

		/**
		 * Updates/Substitutes a value at a specified 0-based index in the Binary
		 * Indexed Tree.
		 * 
		 * @param index the 0-based index to be updated/substituted
		 * @param value the new value
		 */
		public void update(int index, long value) {
			validate(index);
			final long diff = value - vals[index];
			add(index, diff);
		}

		/**
		 * Adds a value at a specified 0-based index in the Binary Indexed Tree.
		 * 
		 * @param i     the 0-based index to be updated
		 * @param value the new value
		 */
		public void add(int i, long value) {
			validate(i);
			vals[i] += value;
			for (++i; i <= size; i += i & -i)
				tree[i] += value;
		}

		/**
		 * Returns the sum of vals[0..index].
		 * 
		 * @param i the inclusive 0-based index.
		 * @return the sum of vals[0..index]
		 */
		public long sum(int i) {
			validate(i);
			long sum = 0;
			for (++i; i > 0; i -= i & -i)
				sum += tree[i];
			return sum;
		}

		/**
		 * Returns the sum of vals[start..end].
		 * 
		 * @param start the start index
		 * @param end   the end index
		 * @return the sum of vals[start..end].
		 */
		public long sum(int start, int end) {
			validate(start);
			validate(end);
			if (start > end)
				throw new IllegalArgumentException(
						"start:" + start + " should not be greater than end:" + end);
			return start == 0 ? sum(end) : sum(end) - sum(start - 1);
		}

		public int size() {
			return size;
		}

		@Override
		public String toString() {
			final StringBuilder sb = new StringBuilder();
			for (int i = 0; i < size; i++)
				sb.append("index: ").append(i).append(" value: ").append(vals[i]).append(" sum: ")
						.append(sum(i)).append("\n");
			return sb.toString();
		}

		/**********************************************************************
		 * *
		 * 
		 * PRIVATE METHODS
		 * 
		 * *
		 **********************************************************************/

		/**
		 * Validates a 0 based index with respect to the values array vals.
		 * 
		 * @param index the 0-based index to validate
		 */
		private void validate(int index) {
			if (index < 0 || index >= size)
				throw new IllegalArgumentException(
						"start: " + index + " should be between 0 and " + (size - 1));
		}
	}

	public static void main(String[] args) throws IOException {
		// long start = System.nanoTime();
		solve();
		// System.out.println("Elapsed: " + (System.nanoTime() - start) / 1000000 +
		// "ns");
		out.flush();
	}

	@SuppressWarnings("unused")
	private static class In {
		final private static int BUFFER_SIZE = 1024;
		private byte[] buf;
		private InputStream is;
		private int buflen;
		private int bufptr;

		public In() {
			is = System.in;
			buf = new byte[BUFFER_SIZE];
			buflen = bufptr = 0;
		}

		public In(String input) {
			is = new ByteArrayInputStream(input.getBytes());
			buf = new byte[BUFFER_SIZE];
			buflen = bufptr = 0;
		}

		public int readByte() {
			if (bufptr >= buflen) {
				try {
					buflen = is.read(buf);
				} catch (IOException ioe) {
					throw new InputMismatchException();
				}
				bufptr = 0;
			}
			if (buflen <= 0)
				return -1;
			return buf[bufptr++];
		}

		public boolean isSpaceChar(int c) {
			return !(c >= 33 && c <= 126);
		}

		public int skip() {
			int b;
			while ((b = readByte()) != -1 && isSpaceChar(b))
				;
			return b;
		}

		/* Next character */
		public char nc() {
			return (char) skip();
		}

		/* Next double */
		public double nd() {
			return Double.parseDouble(ns());
		}

		/* Next string */
		public String ns() {
			final StringBuilder sb = new StringBuilder();
			int b = skip();
			while (!isSpaceChar(b)) {
				sb.appendCodePoint(b);
				b = readByte();
			}
			return sb.toString();
		}

		/* Next integer */
		public int ni() {
			boolean minus = false;
			int num = 0;
			int b;
			while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'))
				;
			if (b == '-') {
				minus = true;
				b = readByte();
			}
			while (b >= '0' && b <= '9') {
				num = num * 10 + (b - '0');
				b = readByte();
			}
			return minus ? -num : num;
		}

		/* Next long */
		public long nl() {
			boolean minus = false;
			long num = 0;
			int b;
			while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'))
				;
			if (b == '-') {
				minus = true;
				b = readByte();
			}
			while (b >= '0' && b <= '9') {
				num = num * 10 + (b - '0');
				b = readByte();
			}
			return minus ? -num : num;
		}

		/* Next integer 1D array */
		public Integer[] nia(int n) {
			final Integer[] arr = new Integer[n];
			for (int i = 0; i < n; i++)
				arr[i] = ni();
			return arr;
		}

		/* Next long 1D array */
		public long[] nla(int n) {
			final long[] arr = new long[n];
			for (int i = 0; i < n; i++)
				arr[i] = nl();
			return arr;
		}

		/* Next string 1D array */
		public String[] nsa(int n) {
			final String[] arr = new String[n];
			for (int i = 0; i < n; i++)
				arr[i] = ns();
			return arr;
		}

		/* Next char 1D array */
		public char[] nca(int n) {
			final char[] arr = new char[n];
			for (int i = 0; i < n; i++)
				arr[i] = nc();
			return arr;
		}

		/* Next double 1D array */
		public double[] nda(int n) {
			final double[] arr = new double[n];
			for (int i = 0; i < n; i++)
				arr[i] = nc();
			return arr;
		}

		/* Next integer matrix */
		public int[][] nim(int n, int m) {
			final int[][] arr = new int[n][m];
			for (int i = 0; i < n; i++)
				for (int j = 0; j < m; j++)
					arr[i][j] = ni();
			return arr;
		}

		/* Next long matrix */
		public long[][] nlm(int n, int m) {
			final long[][] arr = new long[n][m];
			for (int i = 0; i < n; i++)
				for (int j = 0; j < m; j++)
					arr[i][j] = nl();
			return arr;
		}

		/* Next string matrix */
		public String[][] nsm(int n, int m) {
			final String[][] arr = new String[n][m];
			for (int i = 0; i < n; i++)
				for (int j = 0; j < m; j++)
					arr[i][j] = ns();
			return arr;
		}

		/* Next char matrix */
		public char[][] ncm(int n, int m) {
			final char[][] arr = new char[n][m];
			for (int i = 0; i < n; i++)
				for (int j = 0; j < m; j++)
					arr[i][j] = nc();
			return arr;
		}

		/* Next double matrix */
		public double[][] ndm(int n, int m) {
			final double[][] arr = new double[n][m];
			for (int i = 0; i < n; i++)
				for (int j = 0; j < m; j++)
					arr[i][j] = nd();
			return arr;
		}

		public static void log(Object... o) {
			System.out.println(Arrays.deepToString(o));
		}
	}

}