github.com/captn3m0/codechef.git

---
category_name: easy
problem_code: DEVCLASS
problem_name: 'Devu and his Class'
languages_supported:
    - ADA
    - ASM
    - BASH
    - BF
    - C
    - 'C99 strict'
    - CAML
    - CLOJ
    - CLPS
    - 'CPP 4.3.2'
    - 'CPP 4.9.2'
    - CPP14
    - CS2
    - D
    - ERL
    - FORT
    - FS
    - GO
    - HASK
    - ICK
    - ICON
    - JAVA
    - JS
    - 'LISP clisp'
    - 'LISP sbcl'
    - LUA
    - NEM
    - NICE
    - NODEJS
    - 'PAS fpc'
    - 'PAS gpc'
    - PERL
    - PERL6
    - PHP
    - PIKE
    - PRLG
    - PYTH
    - 'PYTH 3.4'
    - RUBY
    - SCALA
    - 'SCM guile'
    - 'SCM qobi'
    - ST
    - TCL
    - TEXT
    - WSPC
max_timelimit: '2'
source_sizelimit: '50000'
problem_author: admin2
problem_tester: laycurse
date_added: 23-12-2014
tags:
    - ad
    - admin2
    - easy
    - greedy
    - march15
editorial_url: 'http://discuss.codechef.com/problems/DEVCLASS'
time:
    view_start_date: 1426498200
    submit_start_date: 1426498200
    visible_start_date: 1426498200
    end_date: 1735669800
    current: 1493558135
layout: problem
---
All submissions for this problem are available.###  Read problems statements in [Mandarin Chinese](http://www.codechef.com/download/translated/MARCH15/mandarin/DEVCLASS.pdf) and [Russian](http://www.codechef.com/download/translated/MARCH15/russian/DEVCLASS.pdf).

Devu is a class teacher of a class of **n** students. One day, in the morning prayer of the school, all the students of his class were standing in a line. You are given information of their arrangement by a string **s**. The string **s** consists of only letters **'B'** and **'G'**, where **'B'** represents a boy and **'G'** represents a girl.

Devu wants inter-gender interaction among his class should to be maximum. So he does not like seeing two or more boys/girls standing nearby (i.e. continuous) in the line. e.g. he does not like the arrangements **BBG** and **GBB**, but he likes **BG**, **GBG** etc.

Now by seeing the initial arrangement **s** of students, Devu may get furious and now he wants to change this arrangement into a likable arrangement. For achieving that, he can swap positions of any two students (not necessary continuous). Let the cost of swapping people from position **i** with position **j** (**i ≠ j**) be **c(i, j)**. You are provided an integer variable **type**, then the cost of the the swap will be defined by **c(i, j) = |j − i|type**.

Please help Devu in finding minimum cost of swaps needed to convert the current arrangement into a likable one.

### Input

The first line of input contains an integer **T**, denoting the number of test cases. Then **T** test cases are follow.

The first line of each test case contains an integer **type**, denoting the type of the cost function. Then the next line contains string **s** of length **n**, denoting the initial arrangement **s** of students.

Note that the integer **n** is not given explicitly in input.

### Output

For each test case, print a single line containing the answer of the test case, that is, the minimum cost to convert the current arrangement into a likable one. If it is not possible to convert the current arrangement into a likable one, then print **-1** instead of the minimum cost.

### Constraints and Subtasks

**Subtask 1: 25 points**

- **1 ≤ T ≤ 105**
- **1 ≤ n ≤ 105**
- **type = 0**
- Sum of **n** over all the test cases in one test file does not exceed **106.**

**Subtask 2: 25 points**

- **1 ≤ T ≤ 105**
- **1 ≤ n ≤ 105**
- **type = 1**
- Sum of **n** over all the test cases in one test file does not exceed **106.**

**Subtask 3: 25 points**

- **1 ≤ T ≤ 105**
- **1 ≤ n ≤ 105**
- **type = 2**
- Sum of **n** over all the test cases in one test file does not exceed **106.**

**Subtask 4: 25 points**

- **1 ≤ T ≤ 102**
- **1 ≤ n ≤ 103**
- **type** can be 0, **1** or **2**, that is **type ∈ {0, 1, 2}**.

### Example

<pre><b>Input:</b>
8
0
BB
0
BG
0
BBGG
1
BGG
1
BGGB
1
BBBGG
2
BBGG
2
BGB

<b>Output:</b>
-1
0
1
1
1
3
1
0
</pre>### Explanation

Note **type** of the first **3** test cases is 0. So **c(i, j) = 1**. Hence we just have to count minimum number of swaps needed.

**Example case 1.** There is no way to make sure that both the boys does not stand nearby. So answer is **-1**.

**Example case 2.** Arrangement is already valid. No swap is needed. So answer is 0.

**Example case 3.** Swap boy at position **1** with girl at position **2**. After swap the arrangement will be **BGBG** which is a valid arrangement. So answer is **1**.

Now **type** of the next **3** test cases is **1**. So **c(i, j) = |j − i|**, that is, the absolute value of the difference between **i** and **j**.

**Example case 4.** Swap boy at position 0 with girl at position **1**. After swap the arrangement will be **GBG** which is a valid arrangement. So answer is **|1 - 0| = 1**.

**Example case 5.** Swap boy at position 0 with girl at position **1**. After swap the arrangement will be **GBGB** which is a valid arrangement. So answer is **|1 - 0| = 1**.

**Example case 6.** Swap boy at position **1** with girl at position **4**. After swap the arrangement will be **BGBGB** which is a valid arrangement. So answer is **|4 - 1| = 3**.

Then **type** of the last **2** test cases is **2**. So **c(i, j) = (j − i)2**

**Example case 7.** Swap boy at position **1** with girl at position **2**. After swap the arrangement will be **BGBG** which is a valid arrangement. So answer is **(2 - 1)2 = 1**.

**Example case 8.** Arrangement is already valid. No swap is needed. So answer is 0.