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.io.*;
import java.util.*;
import java.math.*;
import java.math.BigInteger;


public final class A
{    
	static StringBuilder ans=new StringBuilder();
	static FastReader in=new FastReader();
	static ArrayList<ArrayList<Integer>> g,tg;
	static long mod=(long)1e9+7;
	static boolean set[],col[]; 
	static int D[],par[];
	static char G[][];
	static long dp[][],max=0;
	static  HashMap<Integer,Long> buy,sell;
	static boolean T1[][],T2[][];
	static int left[][],right[][];
	static int N;
	//static Pair moves[]= {new Pair(-1,0),new Pair(1,0), new Pair(0,-1), new Pair(0,1)};
	public static void main(String args[])throws IOException
	{		
		int T=i();
		while(T-->0)
		{
			N=i();
			T1=new boolean[2][N+1]; //right is in 1
			T2=new boolean[2][N+1];
			left=new int[2][N+1];
			right=new int[2][N+1];
			for(int i=0; i<2; i++)
			{
				Arrays.fill(left[i], -1);
				Arrays.fill(right[i], -1);
			}
			char X[]=in.next().toCharArray();
			for(int i=0; i<N; i++)
			{
				if(X[i]=='R')
				{
					//this means i can move right and i+1 can't move left
					T1[1][i]=true; //i can move right
					T2[0][i+1]=true; //i+1 can move left in d'
				}
				else
				{
					T1[0][i+1]=true; //i+1 moving left
					T2[1][i]=true; //i moving right
				}
			}
			for(int i=0; i<=N; i++)
			{
				int d=f(i,0);
				ans.append(d+" ");
			}
			ans.append("\n");

		}
		System.out.println(ans);
	}
	static int f(int i,int d)
	{
		int l=left(i,d),r=right(i,d);
		return l+r+1;
	}
	static int left(int i,int d)
	{
		if(canLeft(i,d))
		{
			if(left[d][i]==-1)left[d][i]=1+left(i-1,(d+1)%2);
			return left[d][i];
		}
		return 0;
	}
	static int right(int i,int d)
	{
		if(canRight(i,d))
		{
			if(right[d][i]==-1)right[d][i]=1+right(i+1,(d+1)%2);
			return right[d][i];
		}
		return 0;
	}
	static boolean canLeft(int i,int d)
	{
		if(d==0)
		{
			//we will check in T1
			if(i>=0 && i<=N)
			{
				return T1[0][i];
			}
			return false;
		}
		else
		{
			//we will check in T2
			if(i>=0 && i<=N)
			{
				return T2[0][i];
			}
			return false;
		}
	}
	static boolean canRight(int i,int d)
	{
		if(d==0)
		{
			//we will check in T1
			if(i>=0 && i<=N)
			{
				return T1[1][i];
			}
			return false;
		}
		else
		{
			//we will check in T2
			if(i>=0 && i<=N)
			{
				return T2[1][i];
			}
			return false;
		}
	}
	static char f(char A[])
	{
		int z=0;
		for(char x:A)
			if(x=='0')z++;
		if(z*2>=A.length)return '0';
		else return '1';
	}
	static int lower(long A[],long x)
	{
		int l=-1,r=A.length;
		while(r-l>1)
		{
			int m=(l+r)/2;
			if(A[m]>=x)r=m;
			else l=m;				
		}
		return r;
	}
	static int upper(long A[],long x)
	{
		int l=-1,r=A.length;
		while(r-l>1)
		{
			int m=(l+r)/2;
			if(A[m]<=x)l=m;
			else r=m;
		}
		return l;
	}



	static boolean f(int a,int b,int c,int d)
	{
		if(a==b && a==c && a==d)return true;
		else return false;
	}
	static int max(int a ,int b,int c,int d)
	{
		a=Math.max(a, b);
		c=Math.max(c,d);
		return Math.max(a, c);
	}
	static int min(int a ,int b,int c,int d)
	{
		a=Math.min(a, b);
		c=Math.min(c,d);
		return Math.min(a, c);
	}


	static int find(int l,int r,long A[] ,long val)
	{
		int m=0;
		while(l<=r)
		{
			m=(l+r)/2;
			if(A[m]>=val)r=m-1;
			else l=m+1;
		}
		return m;
	}
	static void dfs(int n,int p)
	{
		par[n]=p;
		set[n]=true;
		for(int c:g.get(n))
		{
			if(!set[c])dfs(c,n);
		}
	}
	static HashMap<Integer,Integer> Hash(int A[])
	{
		HashMap<Integer,Integer> mp=new HashMap<>();
		for(int a:A)
		{
			int f=mp.getOrDefault(a,0)+1;
			mp.put(a, f);
		}
		return mp;
	}
	static long mul(long a, long b)
	{
		return ( a %mod * 1L * b%mod )%mod;
	}
	static void swap(int A[],int a,int b)
	{
		int t=A[a];
		A[a]=A[b];
		A[b]=t;
	}


	static int find(int a)
	{
		if(par[a]<0)return a;
		return par[a]=find(par[a]);
	}
	static void union(int a,int b)
	{
		a=find(a);
		b=find(b);
		int t=Math.min(a, b);
		b=Math.max(a, b);
		a=t;
		if(a!=b)
		{
			//			g.get(a).add(b);
			//			g.get(b).add(a);
			par[a]+=par[b];
			par[b]=a;
		}
	}
	static boolean isSorted(int A[])
	{
		for(int i=1; i<A.length; i++)
		{
			if(A[i]<A[i-1])return false;
		}
		return true;
	}

	static boolean isDivisible(StringBuilder X,int i,long num)
	{
		long r=0;
		for(; i<X.length(); i++)
		{
			r=r*10+(X.charAt(i)-'0');
			r=r%num;
		}
		return r==0;
	}    



	static int lower_Bound(int A[],int low,int high, int x) 
	{ 
		if (low > high) 
			if (x >= A[high]) 
				return A[high]; 

		int mid = (low + high) / 2; 

		if (A[mid] == x) 
			return A[mid]; 

		if (mid > 0 && A[mid - 1] <= x && x < A[mid]) 
			return A[mid - 1]; 

		if (x < A[mid]) 
			return lower_Bound( A, low, mid - 1, x); 

		return lower_Bound(A, mid + 1, high, x); 
	} 

	static String f(String A)
	{
		String X="";
		for(int i=A.length()-1; i>=0; i--)
		{
			int c=A.charAt(i)-'0';
			X+=(c+1)%2;
		}
		return X;
	}

	static void sort(long[] a) //check for long
	{
		ArrayList<Long> l=new ArrayList<>();
		for (long i:a) l.add(i);
		Collections.sort(l);
		for (int i=0; i<a.length; i++) a[i]=l.get(i);
	}

	static String swap(String X,int i,int j)
	{
		char ch[]=X.toCharArray();
		char a=ch[i];
		ch[i]=ch[j];
		ch[j]=a;
		return new String(ch);
	}

	static int sD(long n)  
	{  

		if (n % 2 == 0 )  
			return 2;  

		for (int i = 3; i * i <= n; i += 2) {  
			if (n % i == 0 )  
				return i;  
		}  

		return (int)n;  
	}  

	static void setGraph(int N)
	{
		par=new int[N+1];
		D=new int[N+1];
		set=new boolean[N+1];
		g=new ArrayList<ArrayList<Integer>>();
		tg=new ArrayList<ArrayList<Integer>>();
		int inf=Integer.MAX_VALUE;
		for(int i=0; i<=N; i++)
		{

			g.add(new ArrayList<Integer>());
			tg.add(new ArrayList<Integer>());			
			D[i]=inf;
		}
	}



	static  long pow(long a,long b)
	{
		//long mod=1000000007;
		long pow=1;
		long x=a;
		while(b!=0)
		{
			if((b&1)!=0)pow=(pow*x)%mod;
			x=(x*x)%mod;
			b/=2;
		}
		return pow;
	}

	static long toggleBits(long x)//one's complement || Toggle bits
	{
		int n=(int)(Math.floor(Math.log(x)/Math.log(2)))+1;

		return ((1<<n)-1)^x;
	}

	static int countBits(long a)
	{
		return (int)(Math.log(a)/Math.log(2)+1);
	}

	static long fact(long N)
	{ 
		long n=2; 
		if(N<=1)return 1;
		else
		{
			for(int i=3; i<=N; i++)n=(n*i)%mod;
		}
		return n;
	}

	static int kadane(int A[])
	{
		int lsum=A[0],gsum=A[0];
		for(int i=1; i<A.length; i++)
		{
			lsum=Math.max(lsum+A[i],A[i]);
			gsum=Math.max(gsum,lsum);
		}
		return gsum;
	}

	static void sort(int[] a) {
		ArrayList<Integer> l=new ArrayList<>();
		for (int i:a) l.add(i);
		Collections.sort(l);
		for (int i=0; i<a.length; i++) a[i]=l.get(i);
	}

	static boolean isPrime(long N)
	{
		if (N<=1)  return false; 
		if (N<=3)  return true; 
		if (N%2 == 0 || N%3 == 0) return false; 
		for (int i=5; i*i<=N; i=i+6) 
			if (N%i == 0 || N%(i+2) == 0) 
				return false; 
		return true; 
	}
	static void print(char A[])
	{
		for(char c:A)System.out.print(c+" ");
		System.out.println();
	}
	static void print(boolean A[])
	{
		for(boolean c:A)System.out.print(c+" ");
		System.out.println();
	}
	static void print(int A[])
	{
		for(int a:A)System.out.print(a+" ");
		System.out.println();	
	}
	static void print(long A[])
	{
		for(long i:A)System.out.print(i+ " ");
		System.out.println();

	}
	static void print(ArrayList<Integer> A)
	{
		for(int a:A)System.out.print(a+" ");
		System.out.println();
	}

	static int i()
	{
		return in.nextInt();
	}

	static long l()
	{
		return in.nextLong();
	}

	static int[] input(int N){
		int A[]=new int[N];
		for(int i=0; i<N; i++)
		{
			A[i]=in.nextInt();
		}
		return A;
	}

	static long[] inputLong(int N)     {
		long A[]=new long[N];
		for(int i=0; i<A.length; i++)A[i]=in.nextLong();
		return A;
	}

	static long GCD(long a,long b) 
	{
		if(b==0)
		{
			return a;
		}
		else return GCD(b,a%b );
	}

}
class cube implements Comparable<cube>
{
	boolean f;
	int p;
	long q;
	cube(long q,int p,boolean f)
	{
		this.q=q;
		this.p=p;
		this.f=f;
	}
	public int compareTo(cube X)
	{
		return X.p-this.p;
	}
}
//class pair implements Comparable<pair>
//{
//	long a;
//	int index;
//	pair(long x,int i)
//	{
//		a=x;
//		index=i;
//	}
//	public int compareTo(pair X)
//	{
//		if(this.a>X.a)return 1;
//		else if(this.a==X.a)return 0;
//		else return -1;
//	}
//}

//Code For FastReader
//Code For FastReader
//Code For FastReader
//Code For FastReader
class FastReader
{
	BufferedReader br;
	StringTokenizer st;
	public FastReader()
	{
		br=new BufferedReader(new InputStreamReader(System.in));
	}

	String next()
	{
		while(st==null || !st.hasMoreElements())
		{
			try
			{
				st=new StringTokenizer(br.readLine());
			}
			catch(IOException e)
			{
				e.printStackTrace();
			}
		}
		return st.nextToken();
	}

	int nextInt()
	{
		return Integer.parseInt(next());
	}

	long nextLong()
	{
		return Long.parseLong(next());
	}

	double nextDouble()
	{
		return Double.parseDouble(next());
	}

	String nextLine()
	{
		String str="";
		try
		{
			str=br.readLine();
		}
		catch (IOException e)
		{
			e.printStackTrace();
		}
		return str;
	}

}