CF1476D.Journey

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 \in [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$.

共有 $n + 1$ 座城市，编号从 $0$ 到 $n$。有 $n$ 条道路连接这些城市，其中第 $i$ 条道路连接城市 $i - 1$ 和城市 $i$（$i \in [1, n]$）。

每条道路具有一个方向。这些方向由一个长度为 $n$ 的字符串给出，字符串中每个字符为 L 或 R。若第 $i$ 个字符为 L，表示第 $i$ 条道路初始方向为从城市 $i$ 指向城市 $i - 1$；否则（即为 R），其初始方向为从城市 $i - 1$ 指向城市 $i$。

一名旅行者希望尽可能多地访问该国的城市。初始时，旅行者将选择某座城市作为旅程起点。每天，旅行者必须从当前所在城市沿一条道路前往一个相邻城市；但仅当该道路的方向与旅行者行进方向一致时，才允许通行。例如：若某条道路方向为从城市 $i$ 指向城市 $i + 1$，则可从 $i$ 走到 $i + 1$，但不可反向从 $i + 1$ 走到 $i$。旅行者每次移动到相邻城市后，所有道路的方向均立即翻转（即 L 变为 R，R 变为 L）。若旅行者无法从当前城市沿任一道路前往相邻城市，则旅程结束；此外，旅行者也可在任意时刻主动终止旅程。

旅行者的目标是访问尽可能多的互不相同的城市（同一城市可被多次访问，但仅首次访问计入总数）。对每座城市 $i$，请计算：若旅行者恰好从城市 $i$ 出发进行一次旅程，所能访问的不同城市的最大数量。

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

Each test case consists of two lines. The first line contains one integer $n$ ($1 \le n \le 3 \cdot 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 \cdot 10^5$.

第一行包含一个整数 $t$（$1 \le t \le 10^4$）—— 测试用例的数量。

每个测试用例由两行组成。第一行包含一个整数 $n$（$1 \le n \le 3 \cdot 10^5$）。第二行包含一个长度恰好为 $n$ 的字符串 $s$，其中每个字符均为 L 或 R。

保证所有测试用例的 $n$ 之和不超过 $3 \cdot 10^5$。

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.

对于每个测试用例，输出 $n + 1$ 个整数。其中第 $i$ 个整数应等于旅行者在一次旅程中最多能够访问的不同城市的数量，前提是该旅程从第 $i$ 个城市出发。