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 java.io.*;
import java.math.BigInteger;
public class Mamo {
	//  Solution 
    public static void main(String [] args) throws IOException {
    	//Dir by MohammedElkady
    	int tt=in.nextInt();
    	while(tt-->0) {
    		int n;
    		n = in.nextInt();
    		String s = in.s();
    		int[] left = new int[n];
    		int[] right = new int[n];
    		int[] ans = new int[n + 1];
    		left[0] = 0;
    		for(int i = 1; i < n; i++) {
    			if(s.charAt(i) != s.charAt(i - 1)) left[i] = left[i - 1]; else left[i] = i; }
    		right[n - 1] = n - 1;
    		for(int i = n - 2; i >= 0; i--) {
    			if(s.charAt(i) != s.charAt(i + 1)) right[i] = right[i + 1]; else right[i] = i;
    		}
     
    		for(int i = 0; i <= n; i++) {
    			ans[i] = 1;
    			if(i < n && s.charAt(i) == 'R') {
    				ans[i] = Math.max(ans[i], right[i] - left[i] + 2);}
    			if(i > 0 && s.charAt(i - 1) == 'L') {ans[i] = Math.max(ans[i], right[i - 1] - left[i - 1] + 2);}}
     
    		for(int i = 0; i <= n; i++) {
    			out.append(ans[i] + " ");
    		}
     out.append("\n");
    	}
    	out.close();
    }
    static long mod=1000000007L;
    static long gcd(long a,long b) {
    	if(a==0)
    		return b;
    	return gcd(b%a,a);
    }
    static long dp[][][];
    static long vor(int i, int u,int t) {
    	if(t>1)
    		return -1;
    	if(dp[i][u][t]!=0) 
    		return dp[i][u][t];
    	long a=vor(i-1,u-1,t),b=vor(i-1,u-1,t);
    	
    	return 0;
    }
    static Reader in=new Reader();
    public static PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
    static class Reader 
    { 
        private InputStream mIs;private byte[] buf = new byte[1024];private int curChar,numChars;public Reader() { this(System.in); }public Reader(InputStream is) { mIs = is;} 
        public int read() {if (numChars == -1) throw new InputMismatchException();if (curChar >= numChars) {curChar = 0;try { numChars = mIs.read(buf);} catch (IOException e) { throw new InputMismatchException();}if (numChars <= 0) return -1; }return buf[curChar++];} 
        public String nextLine(){int c = read();while (isSpaceChar(c)) c = read();StringBuilder res = new StringBuilder();do {res.appendCodePoint(c);c = read();}while (!isEndOfLine(c));return res.toString() ;} 
        public String s(){int c = read();while (isSpaceChar(c)) c = read();StringBuilder res = new StringBuilder();do {res.appendCodePoint(c);c = read();}while (!isSpaceChar(c));return res.toString();} 
        public long l(){int c = read();while (isSpaceChar(c)) c = read();int sgn = 1;if (c == '-') { sgn = -1 ; c = read() ; }long res = 0; do{ if (c < '0' || c > '9') throw new InputMismatchException();res *= 10 ; res += c - '0' ; c = read();}while(!isSpaceChar(c));return res * sgn;} 
        public int nextInt(){int c = read() ;while (isSpaceChar(c)) c = read();int sgn = 1;if (c == '-') { sgn = -1 ; c = read() ; }int res = 0;do{if (c < '0' || c > '9') throw new InputMismatchException();res *= 10 ; res += c - '0' ; c = read() ;}while(!isSpaceChar(c));return res * sgn;} 
        public double d() throws IOException {return Double.parseDouble(s()) ;}
        public boolean isSpaceChar(int c) { return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1; } 
        public boolean isEndOfLine(int c) { return c == '\n' || c == '\r' || c == -1; } 
        public int[] arr(int n){int[] ret = new int[n];for (int i = 0; i < n; i++) {ret[i] = nextInt();}return ret;}
    }
}
class node implements Comparable<node> {
int val,pos;
node(int val,int pos){
	this.pos=pos;this.val=val;
}
@Override
public int compareTo(node o) {
	
	return val-o.val;
}


}
class xtree{
	public xtree(int n,int a[]) {
		this.a=a;
		seg=new int[n*4];
		//lazy=new int[n*4];
		build(1,0,n-1);
	}
	int seg[], a[],lazy[];
	    void check(int p,int s,int e) {
	        if(lazy[p]!=0) {
	            seg[p] += lazy[p];
	            if(s!=e) {
	                lazy[2*p] += lazy[p];
	                lazy[2*p+1] += lazy[p];
	            }
	            lazy[p] = 0;
	        }
	    }
	    
	     void build(int p,int s,int e) {
	        //check(p,s,e);
	        
	        if(s==e) {
	            seg[p] = a[s];
	            return;
	        }
	        
	        build(2*p,s,(s+e)/2);
	        build(2*p+1,(s+e)/2+1,e);
	        
	        seg[p] = seg[2*p]+ seg[2*p+1];
	    }
	    
	   void update(int p,int s,int e,int i,int v) {
	       // check(p,s,e);
	        
	        if(s==e) {
	            seg[p] = v;
	            return;
	        }
	        
	        if(i<=(s+e)/2) update(2*p,s,(s+e)/2,i,v);
	        else update(2*p+1,(s+e)/2+1,e,i,v);
	        
	        seg[p] = seg[2*p]+seg[2*p+1];
	    }
	    
	     void update(int p,int s,int e,int a,int b,int v) {
	        //check(p,s,e);
	        
	        if(s>=a && e<=b) {
	            seg[p] += v;
	            
	            if(s!=e) {
	                lazy[2*p] += v;
	                lazy[2*p+1] += v;
	            }
	            
	            return;
	        }
	        
	        if(s>b || e<a)
	            return;
	        
	        update(2*p,s,(s+e)/2,a,b,v);
	        update(2*p+1,(s+e)/2+1,e,a,b,v);
	        
	        seg[p] = seg[2*p]+seg[2*p+1];
	    }
    
 
    
    int get(int p,int s,int e,int a,int b) {
        if(s>=a && e<=b)
            return seg[p];
        
        if(s>b || e<a)
            return 0; 
        
        return get(2*p,s,(s+e)/2,a,b)+ get(2*p+1,(s+e)/2+1,e,a,b);
    }
}

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;
        }
}
 
class Sorting{
 
 public static int[] bucketSort(int[] array, int bucketCount) {
 
 if (bucketCount <= 0) throw new IllegalArgumentException("Invalid bucket count");
 
 if (array.length <= 1) return array; //trivially sorted
 
 
 
 long high = array[0];
 
 long low = array[0];
 
 for (int i = 1; i < array.length; i++) { //find the range of input elements
 
 if (array[i] > high) high = array[i];
 
 if (array[i] < low) low = array[i];
 
 }
 
 double interval = ((double)(high - low + 1))/bucketCount; //range of one bucket
 
 
 ArrayList<Integer> buckets[] = new ArrayList[bucketCount];
 
 for (int i = 0; i < bucketCount; i++) { //initialize buckets
 
 buckets[i] = new ArrayList();
 
 }
 
 
 
 for (int i = 0; i < array.length; i++) { //partition the input array
 
 buckets[(int)((array[i] - low)/interval)].add(array[i]);
 
 }
 
 
 int pointer = 0;
 
 for (int i = 0; i < buckets.length; i++) {
 
 Collections.sort(buckets[i]); //mergeSort
 
 for (int j = 0; j < buckets[i].size(); j++) { //merge the buckets
 
 array[pointer] = buckets[i].get(j);
 
 pointer++;
 
 }
 
}
 
return array;
 
}
}
 class LongestCommonSubsequence 
{ 
  
  /* Returns length of LCS for X[0..m-1], Y[0..n-1] */
	 int lcs( char[] X, char[] Y, int m, int n ,int K) 
	  { 
		 int L[][] = new int[m+1][n+1]; 
		 int ans[][]=new int[m+1][n+1];
		 int min[][] = new int[m+1][n+1]; 
		 for(int i=0;i<=n;i++) 
			 for(int j=0;j<=m;j++) 
				 min[j][i]='z'+1;
	    /* Following steps build L[m+1][n+1] in bottom up fashion. Note 
	         that L[i][j] contains length of LCS of X[0..i-1] and Y[0..j-1] */
	    for (int i=0; i<=m; i++) 
	    { 
	      for (int j=0; j<=n; j++)
	      { 
	        if (i == 0 || j == 0) 
	            L[i][j] = 0; 
	        else if (X[i-1] == Y[j-1]) { 
	            L[i][j] = L[i-1][j-1] + 1; 
	            ans[i][j]=ans[i-1][j-1]+X[i-1];
	         
	        }
	        else {
	            L[i][j] = max(L[i-1][j], L[i][j-1]); }
	      } 
	    } 
	  return L[m][n]; 
	  } 
	  
	  /* Utility function to get max of 2 integers */
	  int max(int a, int b) 
	  { 
	    return (a > b)? a : b; 
	  } 

     // Returns length of LCS for X[0..m-1], Y[0..n-1] 
     static String lcs(String X, String Y, int m, int n) 
     { 
         int[][] L = new int[m+1][n+1]; 
    
         // Following steps build L[m+1][n+1] in bottom up fashion. Note 
         // that L[i][j] contains length of LCS of X[0..i-1] and Y[0..j-1]  
         for (int i=0; i<=m; i++) 
         { 
             for (int j=0; j<=n; j++) 
             { 
                 if (i == 0 || j == 0) 
                     L[i][j] = 0; 
                 else if (X.charAt(i-1) == Y.charAt(j-1)) 
                     L[i][j] = L[i-1][j-1] + 1; 
                 else
                     L[i][j] = Math.max(L[i-1][j], L[i][j-1]); 
             } 
         } 
    
         // Following code is used to print LCS 
         int index = L[m][n]; 
         int temp = index; 
    
         // Create a character array to store the lcs string 
         char[] lcs = new char[index+1]; 
         lcs[index] = '\u0000'; // Set the terminating character 
    
         // Start from the right-most-bottom-most corner and 
         // one by one store characters in lcs[] 
         int i = m; 
         int j = n; 
         while (i > 0 && j > 0) 
         { 
             // If current character in X[] and Y are same, then 
             // current character is part of LCS 
             if (X.charAt(i-1) == Y.charAt(j-1)) 
             { 
                 // Put current character in result 
                 lcs[index-1] = X.charAt(i-1);  
                   
                 // reduce values of i, j and index 
                 i--;  
                 j--;  
                 index--;      
             } 
    
             // If not same, then find the larger of two and 
             // go in the direction of larger value 
             else if (L[i-1][j] > L[i][j-1]) 
                 i--; 
             else
                 j--; 
         } 
    
         // Print the lcs 
         StringBuilder Sd=new StringBuilder();
         for(int k=0;k<=temp;k++) 
             Sd.append(lcs[k]); 
      return Sd.toString();   
     }
 }