Attempt

Please login to see your submissions result.

Problem

Trên quảng trường lễ hội, các hội đoàn bày một dãy quân trụ lễ (như quân cờ domino) thẳng hàng, đánh số từ trái sang phải ~1, 2, \ldots, n~. Mỗi quân trụ có thể được phù thủy gió hô nghiêng về trái hoặc hô nghiêng về phải; những quân không bị gọi sẽ đứng yên.
Sau hồi trống, phép gọi đồng thời phát tác:

• Nếu một quân trụ nghiêng sang trái, nó lập tức xô quân trụ kề bên bên trái (nếu quân ấy vẫn đứng), rồi sức xô truyền tiếp từng bước về trái.
• Tương tự, quân nghiêng sang phải xô về phía bên phải.
• Nếu tại một thời điểm hai luồng xô cùng chạm tới cùng một quân từ hai phía đối nghịch, quân đó giữ thăng bằng và đứng yên.

Bạn được cho trạng thái gọi ban đầu của ~n~ quân trụ. Sau khi hiệu ứng kết thúc, có bao nhiêu quân trụ vẫn đứng yên?

Input

• Dòng đầu: số bộ test ~T~ ~(1 \le T \le 10^3)~.
• Với mỗi test:
  • Dòng 1: số nguyên ~n~ ~(1 \le n \le 10^5)~ — số quân trụ.
  • Dòng 2: một chuỗi dài ~n~ ký tự mô tả lệnh gọi ban đầu:
  • 'L': quân trụ bị gọi nghiêng về trái,
  • 'R': quân trụ bị gọi nghiêng về phải,
  • '.': quân trụ không bị gọi.

Tổng độ dài của tất cả chuỗi trong dữ liệu không vượt quá ~10^5~.

Output

Với mỗi test, in một số nguyên — số quân trụ đứng yên sau khi mọi hiệu ứng kết thúc.

Sample