In the Adelaide Competitive Programming Club, members have been spreading rumours about each other in an attempt to gain influence in the lead-up to becoming president. These claims circulate through aucpl.com, Discord, and in-person events, and as the club's HR officer, you have been assigned to monitor and control the situation before it affects the upcoming AGM.

Each statement claims something about a person. Some statements are guaranteed to be true, while others may be lies. For every person, at most one distinct claim can be true.

Multiple identical statements may appear, and each input line is treated as a separate statement occurrence. If a statement is false, that occurrence counts as one lie.

It is guaranteed that the gospel statements are consistent, no person will have two different gospel claims.

Your task is to determine the minimum possible number of lies, so that you can decide how to handle the misinformation and restore order before the AGM.

Input

The first line contains an integer, ~n~ ~(1 \leq n \leq 4\times 10^4)~, the number of statements.

The next ~n~ lines each contain a statement of the form a b c, where:

• ~a \in \{1, 2\}~ is the statement type.
• ~b~ is the person's name, a single lowercase word of at most 20 characters.

• ~c~ is the claim, a single lowercase word of at most 20 characters, which may contain hyphens.

• A type 1 statement (Gossip) may be true or false.

• A type 2 statement (Gospel) is always true.

Output

Output a single integer - the minimum number of lies you must have received.

Example

Input 1

5
1 patrick likes-cats
1 patrick likes-dogs
2 tom likes-birds
1 tom likes-cows
1 patrick likes-dogs

Output 1

2

Since the gospel states that Tom likes birds, the gossip claiming he likes cows must be a lie. Patrick has two gossip statements about him but only one can be true. Since we are trying to minimise total lies, we choose likes-dogs to be the true one since it occurs more than likes-cats. Thus there are a total of ~1+1=2~ minimum lies.

Input 2

8
2 zara loves-hiking
1 zara loves-hiking
1 zara hates-hiking
1 zara hates-hiking
1 mike plays-chess
1 mike plays-chess
1 mike plays-chess
1 mike reads-books

Output 2

3

Zara's gospel locks in loves-hiking, so her two hates-hiking gossips are both lies. Mike has no gospel and plays-chess appears 3 times, while reads-books appears once, so we should choose plays-chess to be the truth to minimise the number of lies. Thus there are ~2+1=3~ total minimum lies.

Input 3

7
1 alice likes-pizza
1 alice likes-pizza
1 alice likes-sushi
1 bob hates-mondays
1 bob hates-mondays
1 bob loves-fridays
1 carol plays-guitar

Output 3

2

It was gossiped that Alice likes-pizza twice, and likes-sushi once, so to minimise lies likes-pizza should be the true statement. It was gossiped that Bob hates-mondays twice and loves-fridays once, so we pick hates-mondays as the truth. Carol only has one gossip about her, so there are not necessarily any lies. Thus the minimum total number of lies is ~1+1=2~.