Roda Gigi

time limit: 1 seconds

memory limit: 32 megabytes

input: standard input

output: standard output

Vincent baru-baru ini memulai usaha baru sebagai seorang pengusaha bengkel. Ketertarikannya terhadap mesin bermotor, membuat dia akhirnya memutuskan untuk membuka usaha tersebut. Sebagai pengusaha baru, tentu Vincent membutuhkan karyawan dalam membantu tugasnya. Namun karena Vincent belum memiliki uang yang cukup banyak, akhirnya Vincent mengangkat anda sebagai karyawan satu-satunya.

Dengan bermodalkan kenalan dekat, akhirnya pelanggan pertama datang. Pelanggan ini mempunyai mesin dengan N buah roda gigi (gear) yang tersusun berderet dan bersentuhan dari kiri ke kanan. Roda gigi ini memiliki diameter yang sama, serta jumlah gerigi yang sama. Permasalahannya adalah, terdapat beberapa roda gigi yang berputar tidak sesuai arahnya ketika mesin dinyalakan.

Setiap roda gigi bisa berputar dalam dua arah: searah jarum jam (CW: clockwise) dan berlawanan dengan arah jarum jam (CCW: counter clockwise). Jika roda gigi pertama berputar ke arah CW dan roda gigi kedua juga berputar ke arah CW, maka kedua roda gigi tersebut akan tersendat dan mesin tersebut tidak akan jalan. Begitu juga sebaliknya, jika kedua roda gigi yang bersebelahan berputar ke arah CCW, maka kedua roda gigi tersebut juga akan tersendat. Mesin tersebut dapat bekerja dengan benar hanya jika setiap roda gigi yang bersebelahan beputar ke arah yang berbeda. Gambar berikut menjelaskan bagaimana keadaan dua roda gigi yang bersebelahan jika arah putarannya berbeda (tidak tersendat).

Kalian diberikan N buah roda gigi dengan kondisi berputar dari masing masing roda gigi ketika mesin dinyalakan. Bantu Vincent menghitung berapa roda gigi minimum yang harus Vincent ubah putarannya agar mesin tersebut berjalan secara normal.

Input

Baris pertama berisi sebuah bilangan T (T ≤ 100) yang menyatakan banyaknya kasus yang harus ditangani. Untuk setiap kasus, berisi sebuah bilangan N (1 ≤ N ≤ 1.000) yang menyatakan jumlah roda gigi. Baris berikutnya berisi string dengan panjang N yang berisi karakter 'R' yang menyatakan roda gigi tersebut berputar searah jarum jam (CW), atau 'L' yang menyatakan roda gigi tersebut berputar berlawanan dengan arah jarum jam (CCW).

Output

Untuk setiap kasus, cetak "Kasus #K: M" dimana K adalah nomor kasus dimulai dari 1, dan M adalah jumlah roda gigi minimum yang harus Vincent ubah putarannya.

Sample Tests
Input

3
2
LR
2
LL
3
LLL

Output

Kasus #1: 0
Kasus #2: 1
Kasus #3: 1

Notes

Penjelasan contoh kasus 1:

Ada dua roda gigi yang bersebelahan dan arah putaran mereka berbeda, sehingga tidak perlu ada perubahan

Penjelasan contoh kasus 2:

Vincent dapat mengubah putaran pada roda gigi pertama menjadi CW/R – RL, ATAU mengubah putaran roda gigi kedua menjadi CW/R – LR.

Penjelasan contoh kasus 3:

Vincent harus mengubah putaran pada roda gigi kedua menjadi CW/R – LRL. Vincent juga bisa mengubah putaran pada roda gigi pertama dan ketiga menjadi CW/R – RLR, agar mesin tersebut bekerja; namun cara ini membutuhkan 2 roda gigi untuk diubah putarannya.


var
n,i,r,j,has:integer;
s:ansistring;
begin
readln(n);
 for j:=1 to n do
 begin
  readln(r);
  readln(s);
  if r > 2 then
  for i:=2 to length(s)-1 do
   begin
   if length(s) >=3 then begin
   if (s[i]=s[i-1]) and (s[i]=s[i+1]) then begin inc(has); s[i]:='a'; end;
   end
   else if length(s) < 3 then begin
   if s[i] = s[i-1] then inc(has);
                              end;
   end;
 writeln('Kasus #',j,': ',has);
 end;
end.