На координатной прямой находится робот. Изначально робот расположен в точке $$$x$$$ ($$$x \ne 0$$$). У робота есть последовательность команд размера $$$n$$$, состоящая из символов, где L представляет собой перемещение влево на одну единицу (из точки $$$p$$$ в точку $$$(p-1)$$$), а R представляет собой перемещение вправо на одну единицу (из точки $$$p$$$ в точку $$$(p+1)$$$).
Робот начинает выполнять эту последовательность команд (по одной команде в секунду, в заданном порядке). Однако каждый раз, когда робот достигает точки $$$0$$$, счетчик выполненных команд сбрасывается (т. е. он начинает выполнять всю последовательность команд с самого начала). Если робот завершил все команды и не находится в точке $$$0$$$, он останавливается.
Ваша задача — подсчитать, сколько раз робот перейдет в точку $$$0$$$ за $$$k$$$ секунд.
Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.
Первая строка каждого набора входных данных содержит три целых числа $$$n$$$, $$$x$$$ и $$$k$$$ ($$$1 \le n \le 2 \cdot 10^5$$$; $$$-n \le x \le n$$$; $$$n \le k \le 10^{18}$$$).
Вторая строка содержит строку $$$s$$$, состоящую из $$$n$$$ символов L и/или R.
Дополнительное ограничение на входные данные: сумма $$$n$$$ по всем наборам входных данных не превышает $$$2 \cdot 10^5$$$.
Для каждого набора входных данных выведите одно целое число — количество раз, когда робот перейдет в точку $$$0$$$ за $$$k$$$ секунд.
63 2 6LLR2 -1 8RL4 -2 5LRRR5 3 7LRRLL1 1 1L3 -1 4846549234412827RLR
1 4 1 0 1 2423274617206414
В первом примере робот движется следующим образом: $$$2 \rightarrow 1 \rightarrow \underline{0} \rightarrow -1 \rightarrow -2 \rightarrow -1$$$. Робот выполнил все инструкции из последовательности и не находится в точке $$$0$$$. Поэтому он остановился через $$$5$$$ секунд, и точка $$$0$$$ была достигнута один раз.
Во втором примере робот движется следующим образом: $$$-1 \rightarrow \underline{0} \rightarrow 1 \rightarrow \underline{0} \rightarrow 1 \rightarrow \underline{0} \rightarrow 1 \rightarrow \underline{0} \rightarrow 1$$$. Робот работал $$$8$$$ секунд, и точка $$$0$$$ была достигнута $$$4$$$ раза.
В третьем примере робот движется следующим образом: $$$-2 \rightarrow -3 \rightarrow -2 \rightarrow -1 \rightarrow \underline{0} \rightarrow -1$$$. Робот работал $$$5$$$ секунд, и точка $$$0$$$ была достигнута один раз.
В четвертом примере робот движется следующим образом: $$$3 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 3 \rightarrow 2$$$. Робот выполнил все инструкции из последовательности и не находится в точке $$$0$$$. Поэтому он остановился через $$$5$$$ секунд, ни разу не достигнув точки $$$0$$$.
