In the snake exhibition, there are n rooms (numbered 0 to n - 1) arranged in a circle, with a snake in each room. The rooms are connected by n conveyor belts, and the i-th conveyor belt connects the rooms i and (i+1) mod n. In the other words, rooms 0 and 1, 1 and 2, …, n-2 and n-1, n-1 and 0 are connected with conveyor belts.

The i-th conveyor belt is in one of three states:

  * If it is clockwise, snakes can only go from room i to (i+1) mod n. 
  * If it is anticlockwise, snakes can only go from room (i+1) mod n to i. 
  * If it is off, snakes can travel in either direction. 

<image>

Above is an example with 4 rooms, where belts 0 and 3 are off, 1 is clockwise, and 2 is anticlockwise.

Each snake wants to leave its room and come back to it later. A room is returnable if the snake there can leave the room, and later come back to it using the conveyor belts. How many such returnable rooms are there?

Input

Each test contains multiple test cases. The first line contains a single integer t (1 ≤ t ≤ 1000): the number of test cases. The description of the test cases follows. 

The first line of each test case description contains a single integer n (2 ≤ n ≤ 300 000): the number of rooms.

The next line of each test case description contains a string s of length n, consisting of only '<', '>' and '-'.

  * If s_{i} =  '>', the i-th conveyor belt goes clockwise. 
  * If s_{i} =  '<', the i-th conveyor belt goes anticlockwise. 
  * If s_{i} =  '-', the i-th conveyor belt is off. 



It is guaranteed that the sum of n among all test cases does not exceed 300 000.

Output

For each test case, output the number of returnable rooms.

Example

Input


4
4
-&gt;&lt;-
5
&gt;&gt;&gt;&gt;&gt;
3
&lt;--
2
&lt;&gt;


Output


3
5
3
0

Note

In the first test case, all rooms are returnable except room 2. The snake in the room 2 is trapped and cannot exit. This test case corresponds to the picture from the problem statement.

In the second test case, all rooms are returnable by traveling on the series of clockwise belts.
import java.util.*;
import java.io.*;
import java.math.*;

public class Main {
	static PrintWriter pw = new PrintWriter(System.out);

	public static void main(String[] args) throws IOException, InterruptedException {
		Scanner sc = new Scanner(System.in);
		int t = sc.nextInt();
		while (t-- > 0) {
			int n = sc.nextInt();
			char[] arr = sc.next().toCharArray();
			Graph g = new Graph(n);
			for (int i = 0; i < arr.length; i++) {
				if (arr[i] == '-') {
					g.addEdge(i, (i + 1) % n);
					g.addEdge((i + 1) % n, i);
				} else if (arr[i] == '>') {
					g.addEdge(i, (i + 1) % n);
				} else {
					g.addEdge((i + 1) % n, i);
				}
			}
			pw.println(g.printSCCs());
		}
		pw.close();
	}

	public static class Graph {
		private int V; // No. of vertices
		private LinkedList<Integer> adj[]; // Adjacency List

		// Constructor
		Graph(int v) {
			V = v;
			adj = new LinkedList[v];
			for (int i = 0; i < v; ++i)
				adj[i] = new LinkedList();
		}

		// Function to add an edge into the graph
		void addEdge(int v, int w) {
			adj[v].add(w);
		}

		static int c;

		// A recursive function to print DFS starting from v
		void DFSUtil(int v, boolean visited[]) {
			// Mark the current node as visited and print it
			visited[v] = true;
			c++;
			int n;

			// Recur for all the vertices adjacent to this vertex
			Iterator<Integer> i = adj[v].iterator();
			while (i.hasNext()) {
				n = i.next();
				if (!visited[n])
					DFSUtil(n, visited);
			}
		}

		// Function that returns reverse (or transpose) of this graph
		Graph getTranspose() {
			Graph g = new Graph(V);
			for (int v = 0; v < V; v++) {
				// Recur for all the vertices adjacent to this vertex
				Iterator<Integer> i = adj[v].listIterator();
				while (i.hasNext())
					g.adj[i.next()].add(v);
			}
			return g;
		}

		void fillOrder(int v, boolean visited[], Stack stack) {
			// Mark the current node as visited and print it
			visited[v] = true;

			// Recur for all the vertices adjacent to this vertex
			Iterator<Integer> i = adj[v].iterator();
			while (i.hasNext()) {
				int n = i.next();
				if (!visited[n])
					fillOrder(n, visited, stack);
			}

			// All vertices reachable from v are processed by now,
			// push v to Stack
			stack.push(new Integer(v));
		}

		// The main function that finds and prints all strongly
		// connected components
		int printSCCs() {
			Stack stack = new Stack();
			int cc = 0;
			// Mark all the vertices as not visited (For first DFS)
			boolean visited[] = new boolean[V];
			for (int i = 0; i < V; i++)
				visited[i] = false;

			// Fill vertices in stack according to their finishing
			// times
			for (int i = 0; i < V; i++)
				if (visited[i] == false)
					fillOrder(i, visited, stack);

			// Create a reversed graph
			Graph gr = getTranspose();

			// Mark all the vertices as not visited (For second DFS)
			for (int i = 0; i < V; i++)
				visited[i] = false;

			// Now process all vertices in order defined by Stack
			while (stack.empty() == false) {
				// Pop a vertex from stack
				int v = (int) stack.pop();

				// Print Strongly connected component of the popped vertex
				if (visited[v] == false) {
					c = 0;
					gr.DFSUtil(v, visited);
					if (c > 1) {
						cc += c;
					}
				}
			}
			return cc;
		}
	}

	public static class pair implements Comparable<pair> {
		long x;
		long y;

		public pair(long x, long y) {
			this.x = x;
			this.y = y;
		}

		public String toString() {
			return x + " " + y;
		}

		public boolean equals(Object o) {
			if (o instanceof pair) {
				pair p = (pair) o;
				return p.x == x && p.y == y;
			}
			return false;
		}

		public int hashCode() {
			return new Double(x).hashCode() * 31 + new Double(y).hashCode();
		}

		public int compareTo(pair other) {
			if (this.x == other.x) {
				return Long.compare(this.y, other.y);
			}
			return Long.compare(this.x, other.x);
		}
	}

	public static class tuble implements Comparable<tuble> {
		int x;
		int y;
		int z;

		public tuble(int x, int y, int z) {
			this.x = x;
			this.y = y;
			this.z = z;
		}

		public String toString() {
			return x + " " + y + " " + z;
		}

		public int compareTo(tuble other) {
			if (this.x == other.x) {
				if (this.y == other.y)
					return this.z - other.z;
				return this.y - other.y;
			} else {
				return this.x - other.x;
			}
		}
	}

	static class Scanner {
		StringTokenizer st;
		BufferedReader br;

		public Scanner(InputStream s) {
			br = new BufferedReader(new InputStreamReader(s));
		}

		public Scanner(FileReader r) {
			br = new BufferedReader(r);
		}

		public boolean hasNext() {
			// TODO Auto-generated method stub
			return false;
		}

		public String next() throws IOException {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}

		public int nextInt() throws IOException {
			return Integer.parseInt(next());
		}

		public long nextLong() throws IOException {
			return Long.parseLong(next());
		}

		public String nextLine() throws IOException {
			return br.readLine();
		}

		public double nextDouble() throws IOException {
			String x = next();
			StringBuilder sb = new StringBuilder("0");
			double res = 0, f = 1;
			boolean dec = false, neg = false;
			int start = 0;
			if (x.charAt(0) == '-') {
				neg = true;
				start++;
			}
			for (int i = start; i < x.length(); i++)
				if (x.charAt(i) == '.') {
					res = Long.parseLong(sb.toString());
					sb = new StringBuilder("0");
					dec = true;
				} else {
					sb.append(x.charAt(i));
					if (dec)
						f *= 10;
				}
			res += Long.parseLong(sb.toString()) / f;
			return res * (neg ? -1 : 1);
		}

		public boolean ready() throws IOException {
			return br.ready();
		}

	}
}