The practice of polygamy is said to have originated 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 marriages results in happiness while the rest believe in arranged marriages.

Whatsoever, it's 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.

Each of the M lines contains two integers: i and j.

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

Output

For each test case, print a single line: "Number of Deaths" (quotes for qualification), followed by a colon(:) and a space, and then a single integer containing 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