B. New Assignment
time limit per test
1.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

There is a class consisting of n students, in which each one has a number representing his/her personality. The teacher gives the students a new assignment and asks them to solve it in groups so that each group can contain two students at most.

Students cannot create groups as they please because the teacher gives the following rules that must be met in order for a group to be valid:

  • The group can be composed of one male student, one female student, or male and female students.
  • If the number of students in the group is two, these students must share common interests. Two students i and j share interests if and only if their numbers ai and aj share common divisor d > 1.

Since this is a really diverse class, no triple of students share a common interest, therefore all triples ai, aj, ak are co-primes (i.e. gcd(ai, aj, ak) ≡ 1).

Your task is to distribute the students into groups such that each student must join exactly one group, and the number of groups is as minimal as possible. Can you?

Input

The first line contains an integer T (1 ≤ T ≤ 100), in which T is the number of test cases.

The first line of each test case contains an integer n (1 ≤ n ≤ 104), in which n is the number of students in the class.

Then a line follows containing n integers a1, a2, ..., an (1 ≤ ai ≤ 106), in which ai if the personality of the ith student. Then a line follows containing n space-separated characters p1, p2, ..., pn (), in which pi is "M" if the ith student is male, and "F" if she is female.

The sum of n overall test cases does not exceed 3 × 105.

Output

For each test case, print a single line containing the minimum number of groups that can be formed in the class.

Example
Input
2
2
3 6
M F
5
5 6 7 10 21
F F F M M
Output
1
3
Note

In the second test case, the minimum number of groups is 3, in which the first group consists of the 1st and 4th students, the second group consists of the 2nd student, and the third group consists of the 3rd and 5th students.