## The Monkey Dance

Input file: a.in
Output file: a.out
Source file: n:\a\a.{c, cpp, pas}

The director of Hind Circus has decided to add a new performance, the monkey dance, to his show. The monkey dance is performed simultaneously by N monkeys. There are N circles drawn on the ground, labelled from 1 to N. In the beginning, each monkey sits on a different circle. There are N arrows drawn from circle to circle in such a way that there is exactly one arrow pointing toward each ring and exactly one arrow pointing away from each ring.

When the show begins, at each whistle of the ringmaster, all the monkeys simultaneously jump from their respective circles to other circles following the arrows from their respective current circles. This is one step of the dance. The dance ends when all the monkeys have returned to the circles where they initially started. How long does the dance last?

Input

The input may have multiple cases. Each case consists of the value of N (1 <= N <= 100) on a line, followed by N lines, each with a pair of integers between 1 and N. The pair I1, I2 means that there is an arrow from circle I1 to circle I2. The input ends with 0 for the value of N.

Output

For each case, simply output the number of steps in the dance. Each output should be on a separate line.

Sample Input

```5
1 2
2 3
3 1
4 5
5 4
4
1 4
2 3
4 1
3 2
0
```

Sample Output

```6
2
```