There are n + 1 cities, numbered from 0 to n. n roads connect these cities, the i-th road connects cities i - 1 and i (i ∈ [1, n]).

Each road has a direction. The directions are given by a string of n characters such that each character is either L or R. If the i-th character is L, it means that the i-th road initially goes from the city i to the city i - 1; otherwise it goes from the city i - 1 to the city i.

A traveler would like to visit as many cities of this country as possible. Initially, they will choose some city to start their journey from. Each day, the traveler must go from the city where they currently are to a neighboring city using one of the roads, and they can go along a road only if it is directed in the same direction they are going; i. e., if a road is directed from city i to the city i + 1, it is possible to travel from i to i + 1, but not from i + 1 to i. After the traveler moves to a neighboring city, all roads change their directions to the opposite ones. If the traveler cannot go from their current city to a neighboring city, their journey ends; it is also possible to end the journey whenever the traveler wants to.

The goal of the traveler is to visit as many different cities as possible (they can visit a city multiple times, but only the first visit is counted). For each city i, calculate the maximum number of different cities the traveler can visit during exactly one journey if they start in the city i. 

Input

The first line contains one integer t (1 ≤ t ≤ 10^4) — the number of test cases.

Each test case consists of two lines. The first line contains one integer n (1 ≤ n ≤ 3 ⋅ 10^5). The second line contains the string s consisting of exactly n characters, each character is either L or R.

It is guaranteed that the sum of n over all test cases does not exceed 3 ⋅ 10^5.

Output

For each test case, print n + 1 integers. The i-th integer should be equal to the maximum number of different cities the traveler can visit during one journey if this journey starts in the i-th city.

Example

Input


2
6
LRRRLL
3
LRL


Output


1 3 2 3 1 3 2
1 4 1 4
import java.util.*;

import javax.swing.text.AbstractDocument.BranchElement;

import java.io.*;

public class C {
	static PrintWriter pw;
	static BufferedReader br;
	static int inf = (int) 1e9;
	static long mod = (long) 1e9 + 7;
	static int[][] memo;
	static boolean[] vis;
	static boolean[][] ok;
	static int[] a;
	static int n, m;
	static ArrayList<Integer>[] adj;
	static ArrayList<Integer> primes;
	static int[] isComposite;

	static void sieve(int N) // O(N log log N)
	{
		isComposite = new int[N + 1];
		isComposite[0] = isComposite[1] = 1; // 0 indicates a prime number
		primes = new ArrayList<Integer>();

		for (int i = 2; i <= N; ++i) // can loop till i*i <= N if primes array is not needed O(N log log sqrt(N))
			if (isComposite[i] == 0) // can loop in 2 and odd integers for slightly better performance
			{
				primes.add(i);
				if (1l * i * i <= N)
					for (int j = i * i; j <= N; j += i) // j = i * 2 will not affect performance too much, may alter in
														// modified sieve
						isComposite[j] = 1;
			}
	}

	static ArrayList<Integer> primeFactors(int N) // O(sqrt(N) / ln sqrt(N))
	{
		ArrayList<Integer> factors = new ArrayList<Integer>(); // take abs(N) in case of -ve integers
		int idx = 0, p = primes.get(idx);

		while (p * p <= N) {
			while (N % p == 0) {
				factors.add(p);
				N /= p;
			}
			p = primes.get(++idx);
		}

		if (N != 1) // last prime factor may be > sqrt(N)
			factors.add(N); // for integers whose largest prime factor has a power of 1
		return factors;
	}

	static int maxFactor(int N) // O(sqrt(N) / ln sqrt(N))
	{ // take abs(N) in case of -ve integers
		int idx = 0, p = primes.get(idx);
		int ans = -1;
		while (p * p <= N) {
			while (N % p == 0) {
				N /= p;
				ans = p;
			}
			p = primes.get(++idx);
		}

		if (N != 1) // last prime factor may be > sqrt(N)
			return N; // for integers whose largest prime factor has a power of 1
		return ans;
	}

	public static void main(String[] args) throws NumberFormatException, IOException, InterruptedException {
		br = new BufferedReader(new InputStreamReader(System.in));
		pw = new PrintWriter(System.out);

		int t = Integer.parseInt(br.readLine());
		while (t-- > 0) {
			int n = Integer.parseInt(br.readLine());
			char[] a = br.readLine().toCharArray();
			int[] l = new int[n];
			int[] r = new int[n];
			l[0] = 1;
			for (int i = 1; i < r.length; i++) {
				if (a[i] != a[i - 1]) {
					l[i] = l[i - 1] + 1;
				} else
					l[i] = 1;
			}
			r[n - 1] = 1;
			for (int i = n - 2; i > -1; i--) {
				if (a[i] != a[i + 1]) {
					r[i] = r[i + 1] + 1;
				} else
					r[i] = 1;
			}
//			System.out.println(Arrays.toString(r));
			for (int i = 0; i < n + 1; i++) {
				int c = 1;
				if (i > 0 && a[i - 1] == 'L')
					c += l[i-1];

				if (i < n && a[i] == 'R')
					c += r[i];
				pw.print(c + " ");
			}
			pw.println();

		}

		pw.flush();
	}

	static ArrayList<Integer> ans;

	static void bfs(int n) {
		Queue<Integer> q = new LinkedList<Integer>();
		q.add(n);
		vis[n] = true;
		int id = 1;
		while (!q.isEmpty()) {
			int size = q.size();
			for (int i = 0; i < size; i++) {
				int u = q.remove();
				if (id % 3 == 0)
					ans.add(u + 1);
				for (int v : adj[u])
					if (!vis[v]) {
						vis[v] = true;
						q.add(v);
					}
			}
			id++;
		}
	}

	static boolean valid(int x, int y) {
		return x > -1 && x < n && y > -1 && y < m;
	}

	static class pair implements Comparable<pair> {
		int x;
		int y;

		public pair(int d, int u) {
			x = d;
			y = u;
		}

		public int compareTo(pair o) {
			if (x == o.x)
				return y - o.y;
			return x - o.x;
		}

	}

	static class pair2 implements Comparable<pair2> {
		int x;
		int y;

		public pair2(int d, int u) {
			x = d;
			y = u;
		}

		public int compareTo(pair2 o) {
			return y - o.y;
		}

	}

	static int[] nxtarr() throws IOException {
		StringTokenizer st = new StringTokenizer(br.readLine());
		int[] a = new int[st.countTokens()];
		for (int i = 0; i < a.length; i++) {
			a[i] = Integer.parseInt(st.nextToken());
		}
		return a;
	}

	static long pow(long a, long e) // O(log e)
	{
		long res = 1;
		while (e > 0) {
			if ((e & 1) == 1)
				res *= a;
			a *= a;
			e >>= 1;
		}
		return res;
	}

	static int gcd(int a, int b) {
		if (a == 0)
			return b;
		return gcd(b % a, a);
	}
}
