Cousin's Aunt

Given a chain of up to ten kinship terms describing how C relates to A, report the maximum and minimum possible degree of kinship between A and C.

Hard8GraphShortest pathBrute forceImplementationNo attempts yetTime limit8sMemory limit512 MB

Problem

Sarah likes reading books. One day she wondered about the family in a mystery novel. The story says:

  • B is A's father's brother's son.
  • C is B's aunt.

Then she asked herself, "so how many degrees of kinship are there between A and C?"

The relation between B and C reads in two ways. C is either the sister of B's father or the sister of B's mother. In the first reading C is the sister of A's father, so C is in the third degree of kinship to A. In the second reading C is the sister of the wife of A's father's brother, so C is in the fifth degree.

You are a friend of Sarah's and you are good at programming. You can help her by writing a program that computes the maximum and the minimum degree of kinship between A and C for a given relation.

The relation between A and C is written as a sequence of these sixteen basic relations: father, mother, son, daughter, husband, wife, brother, sister, grandfather, grandmother, grandson, granddaughter, uncle, aunt, nephew, niece.

The relations mean the following.

  • X's brother is a son of X's father or mother who is not X.
  • X's grandfather is the father of X's father or mother.
  • X's grandson is a son of X's son or daughter.
  • X's uncle is a brother of X's father or mother.
  • X's nephew is a son of X's brother or sister.
  • sister, grandmother, granddaughter, aunt and niece are defined the same way.

Assume the family has none of the following: adoption, marriage between relatives (so the family tree has no cycle), divorce, remarriage, bigamy, same-sex marriage.

The degree of kinship is defined as follows.

  • The distance from X to X's father, mother, son or daughter is one.
  • The distance from X to X's husband or wife is zero.
  • The degree of kinship between X and Y is the shortest distance from X to Y that the rules above give.

Input

The first line has the number of datasets TT (1T2001 \le T \le 200).

Each of the next TT lines holds one dataset in this format.

C is A('s relation)*

Here relation is one of the sixteen words listed above. The asterisk means the part inside the parentheses repeats zero or more times. A dataset holds at most ten relations. Every dataset admits at least one family that matches it.

Output

For each dataset, print the maximum and the minimum degree of kinship between A and C on one line, separated by exactly one space. Print no other characters.