Comparing Your Heroes

Time Limit: 10 Seconds    Memory Limit: 32768 KB

Nowadays many students wouldn't attend classes in university, instead, they stay in dormitory playing Electronic games on computers. One of the most popular games among the boys is KOF (the King Of Fighters), a kind of action game presented by SNK corporation. This series of games becomes so successful that SNK has even created comics and story for it. Although in the story IORI and KYO are the definitely two strongest heroes, it would not affect players' true affection of other characters. Actually, every player has his own favorite heroes.

As a fanatical fan of the KOF game, you're going to help the other players to find out the ranking of their favorite heroes. Players would only provide information of comparisons between the heroes. This sometimes can lead to confusion: maybe not only one ranking satisfies the comparisons. So at first you'd like to find out the number of the rankings that satisfy a specific player's comparisons.

Input

The input consists of several test cases. Each test case begins with a positive integer N on a line, indicating the number of the comparisons. The following N lines are the comparisons between the heroes. Each one is a line containing 2 names of the heroes separated by a space, means the player prefer the first hero to the second. The name of the hero is a sequence of at most 10 upper case letters. No two comparisons would be same, and you can always assure one's favorite heroes would not exceed 16.

Output

For each test case, print out the number of the rankings that satisfy the comparisons on a single line. If no such ranking exists, just print out 0.

Sample Input

4
IORI KYO
MARY SHERMIE
KYO ANDY
SHERMIE ANDY
3
IORI KYO
KYO CLARK
CLARK IORI

Sample Output

6
0

Submit

Source: Zhejiang University Local Contest 2002