N-Step Syllogism

Interview

Time limit2sMemory limit128 MB

Summary

Each premise says all a are b; for each conclusion x is y, decide whether following the implication chain from x reaches y.

Level: Medium4 of 10
Topics: Graph, DFS, Hash map, Implementation
Solved: No attempts yet

Problem

All humans are mortal.

Socrates is a human.

Therefore Socrates is mortal.

The argument above is the standard example of a syllogism. A syllogism is a deductive argument made of two premises and one conclusion. The same reasoning carries over when there are more than two premises.

Every premise has the form a is b and means "all a are b". Given $n$ premises, decide for each of $m$ conclusions whether it is true. A conclusion x is y is true when chaining the premises leads from x to y. For example, if a is b and b is c are premises, then a is c is true.

Input

The first line contains an integer $n$ ( $2 \le n \le 26$ ).

Each of the next $n$ lines contains one premise. Every premise has the form a is b, where a and b are two different lowercase letters. The premise a is b means "all a are b" and never means "all b are a". No letter is the subject of two premises, so a cannot be b and c at the same time. Two different letters a and b can both be c.

Line $n + 2$ contains an integer $m$ ( $1 \le m \le 10$ ). Each of the next $m$ lines contains one conclusion in the same format as a premise.

Output

Print $m$ lines. For each conclusion print T if it is true and F if it is false. A conclusion that cannot be decided counts as false. Print the answers in uppercase.

Examples2

Example 1

Input

3
a is b
b is c
c is d
3
a is d
a is c
d is a

Expected output

T
T
F

Example 2

Input

2
a is b
c is d
3
a is b
a is d
d is c

Expected output

T
F
F