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
// AUTHOR:-  Harsh Thete
//   IIIT-Allahabad
#include <bits/stdc++.h>
using namespace std;

#define ll long long

#define fl(i,a,b) for(ll i=a;i<b;i++)

#define fst ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define TT 	int TT;cin>>TT;while(TT--)

#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define mp make_pair
#define sz size

void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
 
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
 
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
 
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...) 20
#endif

bool prime[1000001];
void SieveOfEratosthenes() 
{ 
    memset(prime, true, sizeof(prime)); 
  
    for (int p=2; p*p<=1000000; p++) 
    { 
        if (prime[p] == true) 
        { 
            for (int i=p*p; i<=1000000; i += p) 
                prime[i] = false; 
        } 
    } 
  
} 

ll biexp(ll x, ll y) 
{ 
    ll res = 1;     
   
    while (y > 0) 
    { 
        if (y & 1) 
            res = res*x; 
   
        y = y>>1; 
        x = x*x;  
    }
    return res; 
}
ll bemo(ll x, ll y, ll m)  
{  
    ll res = 1;  
  
    x = x % m;  
   
    if (x == 0) return 0; 
  
    while (y > 0)  
    {   
        if (y & 1)  
            res = (res*x) % m;  
  
        y = y>>1; 
        x = (x*x) % m;  
    }  
    return res;  
}    
ll maxSubArraySum(ll a[], ll size) 
{ 
    ll max_so_far = INT_MIN, max_ending_here = 0; 
  
    for (ll i = 0; i < size; i++) 
    { 
        max_ending_here = max_ending_here + a[i]; 
        if (max_so_far < max_ending_here) 
            max_so_far = max_ending_here; 
  
        if (max_ending_here < 0) 
            max_ending_here = 0; 
    } 
    return max_so_far; 
}
/*to find sorted array(ascending) in abs number order

                                 also in your code use sort(a,a+n,fun) to get this type of sorted arr*/
bool fun(ll i,ll j)
{
return abs(i)<abs(j);
}

ll ceil_fun(ll x,ll y)
{
return ((x+y-1)/y);                       // returns ceil value 
}

void my_ans_is()
{
   ll n;cin>>n;
   string s;cin>>s;
   ll r[n+1],l[n+1];r[n]=0;
   if(s[n-1]=='R') r[n-1]=1,l[n]=0;
   else r[n-1]=0;
   for(ll i=n-2;i>=0;i--)
   {
       if(s[i]!=s[i+1])
       {
           if(s[i]=='L') r[i]=0;
           else r[i]=r[i+2]+2;
       }
       else
       {
           if(s[i]=='R') r[i]=1;
           else r[i]=0;
       }
   }
   l[0]=0;
   if(s[0]=='L') l[1]=1,r[0]=0;
   else l[1]=0;
   for(ll i=1;i<n;i++)
   {
       if(s[i]!=s[i-1])
       {
           if(s[i]=='L') l[i+1]=l[i-1]+2;
           else l[i+1]=0;
       }
       else
       {
           if(s[i]=='L') l[i+1]=1;
           else l[i+1]=0;
       }
   }
   fl(i,0,n+1) cout<<l[i]+r[i]+1<<" ";
   cout<<"\n";
}
//cin.getline(s,1000) to get string cointaining spaces where s->char s[1000] to find exact len n=strlen(s);
int main() 
{         // Euoiler tot phi(n)=cnt of numbers less than n (from 1to n) whose gcd with n is 1
	     //  for tot cnt of gcd=1 from x to n-> cnt= phi(n/gcd(x,n))
	                                //////////////__gcd(x,y)=__gcd(x-y,y)
	

        fst;
        TT
	{      
         my_ans_is();
// Note:-Check bounds in arrays, check limit of int (signed integer overflow)
        }
   return 0;
}