## Goal

Someone just told you all roads lead to Rome.

As a matter of fact, this is not true.

In order to restore scientific truth, you must write a program that counts the actual number of paths from **Paris** to **Rome**, where cities are visited **at most once**.

To start with, you are given a collection of all paths that directly connect two individual cities and where each city is defined by a number from 1 to 100. **Paris** has **label 1**, and **Rome** has **label 100**.

One may use paths **both ways**.

Let us illustrate the problem with a simple example:

you are given 5 paths:

1 50

50 100

25 50

75 25

100 75

So, we have 5 cities:

- 1 (Paris)

- 25

- 50

- 75

- 100 (Rome)

There are 2 roads from Paris to Rome:

1 -> 50 -> 100

1 -> 50 -> 25 -> 75 -> 100
Input

**Line 1**: An integer `N` corresponding to the total number of paths

`N` next lines: Two integers `A` and `B` corresponding to the two cities the path connects.

Output

The number of roads from Paris to Rome

Constraints

1 ≤ `N` ≤ 100

1 ≤ `A`,`B` ≤ 100

Example

Input

4
1 25
25 50
50 75
75 100