The practice of polygamy is said to have origanted in the Salt Lake City where gender is not an important constraint. In order to obtain a clear count of marriages, each unmarried person living in the city is assigned a unique number. Some believe that love marraiges results in happiness while the rest believe in arranged marriages.

          Whatsoever, its the parents who choose their heir's fiances/fiancees. Once their parents take a decision, their marriage is bound to happen in the near future. But recent studies on this city say that,

1) A marriage between two persons having a difference of belief, results in a divorce.

2) In order to avoid this from happening, some people often change their belief on the day of their marriage.    

    But it is sad to note that, both these scenarios results in a death of one of their well-wishers. Given the information about each unmarried person in the city and their fiances/fiancees, help them so that there is minimum number of deaths.

Input:

The first line contains a single integer T, the number of test cases.

T test cases follow:

The first line of each test case contains two integers, N and M.
N : Number of unmarried persons.
M : Number of pairs for which their marriage has been fixed.

M lines follow:

Each of the M lines contains two integers : i & j

In the following N lines,the belief of each unmarried person is listed, either "Love" or "Arranged" . ( quotes for claification ).

 
Output:

For each test case, print a single line: "Number of Deaths"(quotes for qualification), followed by a colon(:) & a space, and then a single integer containg the minimum number of deaths. Refer the sample output for clarification.

Constraints:

1 <= T <= 100
1 <= N <= 140
1 <=M <=10000
1 <= i <= N
1 <= j <= N

Example:

Input:

1
3 2
1 2
2 3
Love
Arranged
Love

Output:

Number of Deaths: 1