She is an extraordinary girl. She works for a library. Since she is young and cute, she is forced to do a lot of laborious jobs. The most annoying job for her is to put returned books into shelves, carrying them by a cart. The cart is large enough to carry many books, but too heavy for her. Since she is delicate, she wants to walk as short as possible when doing this job. The library has 4N shelves (1 <= N <= 10000), three main passages, and N + 1 sub passages. Each shelf is numbered between 1 to 4N as shown in Figure 1. Horizontal dashed lines correspond to main passages, while vertical dashed lines correspond to sub passages. She starts to return books from the position with white circle in the figure and ends at the position with black circle. For simplicity, assume she can only stop at either the middle of shelves or the intersection of passages. At the middle of shelves, she put books with the same ID as the shelves. For example, when she stops at the middle of shelf 2 and 3, she can put books with ID 2 and 3.

<image>

Since she is so lazy that she doesn’t want to memorize a complicated route, she only walks main passages in forward direction (see an arrow in Figure 1). The walk from an intersection to its adjacent intersections takes 1 cost. It means the walk from the middle of shelves to its adjacent intersection, and vice versa, takes 0.5 cost. You, as only a programmer amoung her friends, are to help her compute the minimum possible cost she takes to put all books in the shelves.



Input

The first line of input contains the number of test cases, T . Then T test cases follow. Each test case consists of two lines. The first line contains the number N , and the second line contains 4N characters, either Y or N . Y in n-th position means there are some books with ID n, and N means no book with ID n.

Output

The output should consists of T lines, each of which contains one integer, the minimum possible cost, for each test case.

Example

Input

2
2
YNNNNYYY
4
NYNNYYNNNYNYYNNN


Output

6
9
#include <iostream>
#include <cstdio>
#include <iomanip>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <bitset>
#include <stack>
#include <utility>
#include <numeric>
#include <algorithm>
#include <functional>
#include <cctype>
#include <complex>
#include <string>
#include <sstream>
#include <fstream>
#include <cassert>
using namespace std;

//common
typedef int  i32;
typedef long long i64,ll;
typedef vector<int> vi; typedef pair<int,int> pii; typedef vector<pair<int,int> > vpii;
typedef long long ll; typedef vector<long long> vl; typedef pair<long long,long long> pll; typedef vector<pair<long long,long long> > vpll;
typedef vector<string> vs; typedef long double ld;

#define BR "\n"
#define ALL(c) (c).begin(),(c).end()
#define REP(i,n) for(int i=0;i<(int)(n);++i)
#define EACH(it,o) for(auto it = (o).begin(); it != (o).end(); ++it)
#define IN(l,v,r) ((l)<=(v) && (v)<(r))

//config
//#undef NDEBUG
//#define INF 1<<30
//#define EPS 1e-8
//const ll MOD =100000007;

//debug
#ifdef NDEBUG
#define DUMP(x)
#define DUMPLN(x)
#define DEBUG(x)
#define DEBUGLN(x)
#define LINE()
#define LINELN()
#define CHECK(exp,act)
#define STOP(e)
#else
#define DUMP(x)  cerr << #x << " = " << (x)
#define DUMPLN(x)  DUMP(x) <<endl
#define DEBUG(x) DUMP(x) << LINE() << " " << __FILE__
#define DEBUGLN(x) DEBUG(x)<<endl
#define LINE()    cerr<< " (L" << __LINE__ << ")"
#define LINELN()    LINE()<<endl
#define CHECK(exp,act)  if(exp!=act){DUMPLN(exp);DEBUGLN(act);}
#define STOP(e)  CHECK(e,true);if(!(e)) exit(1);
#endif

template<class T> inline string toString(const vector<T>& x) {
	stringstream ss;
	REP(i,x.size()){
		if(i!=0)ss<<" ";
		ss<< x[i];
	}
	return ss.str();
}

template<class T> inline string toString(const vector<vector<T> >& map) {
	stringstream ss;
	REP(i,map.size()){
		if(i!=0)ss<<BR;
		ss<< toString(map[i]);
	}
	return ss.str();
}
template<class K,class V>  string toString(map<K,V>& x) {
	string res;stringstream ss;
	for(auto& p:x)ss<< p.first<<":" << p.second<<" ";
	return ss.str();
}

string BITtoString(int bit){
    stringstream ss;
    while(bit!=0){ss<<(bit%2);bit/=2;}
    string res=ss.str();reverse(ALL(res));
    return res;
}

template<typename T,typename V> inline T mod(T v,V MOD){
	return (v%MOD+MOD)%MOD;
}

int INF=1<<28;
class Main{
public:
	void run(){
		//ofstream cout( "out2" );
		int T;cin >>T;
		REP(t,T){
			int N;cin >>N;
			string  s;cin >>s;

			vector<vector<int>> dp(N+1,vector<int>(3,INF));
			
			bool h1=s[0]=='Y';
			bool h2=s[2*N]=='Y';
			dp[0][0]=h2?3:h1?1:0;dp[0][1]=h2?2:1;dp[0][2]=2;
			for(int pos=1;pos<=N;pos++){
				bool h1=s[2*pos-1]=='Y' || (2*pos<2*N && s[2*pos]=='Y' );
				bool h2=s[2*N+2*pos-1]=='Y' || (2*N+2*pos<4*N && s[2*N+2*pos]=='Y');

				dp[pos][0]=min(dp[pos][0],1+dp[pos-1][0]+(h2?3:h1?1:0));
				dp[pos][0]=min(dp[pos][0],1+dp[pos-1][1]+(h2?2:1));
				dp[pos][0]=min(dp[pos][0],1+dp[pos-1][2]+2);
				
				dp[pos][1]=min(dp[pos][1],1+dp[pos-1][0]+(h2?2:1));
				dp[pos][1]=min(dp[pos][1],1+dp[pos-1][1]+((h1&&h2)?2:((h1||h2)?1:0)));
				dp[pos][1]=min(dp[pos][1],1+dp[pos-1][2]+(h1?2:1));
				
				dp[pos][2]=min(dp[pos][2],1+dp[pos-1][0]+2);
				dp[pos][2]=min(dp[pos][2],1+dp[pos-1][1]+(h1?2:1));
				dp[pos][2]=min(dp[pos][2],1+dp[pos-1][2]+(h1?3:h2?1:0));
			}
		//	DUMP(toString(dp));
			cout<<dp[N][0]<<endl;
		}
	}
};
 int main(){
 	Main().run();
 	//Main().main();
 	return 0;
 }