Find the Pisano Period The Fibonacci sequence is a well know sequence in which each entry is the sum of the previous two and the first two entries are 1.  If we take the modulo of each term by a constant the sequence will become periodic.  For example if we took decided to compute the sequence mod 7 we would get the following:

1 1 2 3 5 1 6 0 6 6 5 4 2 6 1 0 1 1 ...


This has a period of 16.  A related sequence, called the Pisano sequence, is defined such that a(n) is the period of the fibonacci sequence when calculated modulo n.

Task

You will should write a program or function that when given n will compute and output the period of the Fibonacci sequence mod n.  That is the nth term in the Pisano sequence.

You must only support integers on the range 0 &lt; n &lt; 2^30

This is a code-golf competition so you should aim to minimize the size of your source code as scored by bytes.

Test cases

1  -&gt; 1
2  -&gt; 3
3  -&gt; 8
4  -&gt; 6
5  -&gt; 20
6  -&gt; 24
7  -&gt; 16
8  -&gt; 12
9  -&gt; 24
10 -&gt; 60
11 -&gt; 10
12 -&gt; 24
GolfScript (28 25 24 23 chars)

~1.{(2$+}{.@+2$%}/+\-,)


Takes input in stdin, leaves it on stdout (or the stack, if you want to further process it...)

This correctly handles the corner cases (Demo).

As a point of interest to GolfScript programmers, I think this is the first program I've written with an unfold which actually came out shorter than the other approaches I tried.