Secret societies attract many people. Incense and dark lights lend a sense of importance to otherwise dull and meaningless experiences, a cynic might say. Most secret societies choose their members based on birth, athletic ability or connections. The Dren Society uses brains and athletic endurance as its criteria.

The major test is a ladder code involving an eight-step ladder. The code consists of climbing the ladder to the top in some particular sequence of step sizes. Each step consists of going to the next rung (step size 1) or skipping one rung (step size 2). So, a possible sequence is 2, 1, 1, 2, 2. This means go directly to the second rung in the first step, then step to the third rung in the second step, then the next one, then up two (skipping a rung), and finally up two again.

Nobody is expected to know the code (it's changed for each applicant). The trick is to climb the ladder repeatedly, acting out different codes in the hope that one of them is the correct sequence. You have to pace yourself to avoid collapsing from exhaustion, but you also have to climb quickly enough that the judges don't reject you out of boredom.

Look at the pattern for ladders of various sizes. For two rungs there are two possibilities:
1, 1
2
That is, go up one at a time or skip directly to the second rung.

For three rungs, there are three possibilities:
1, 1, 1
2, 1
1, 2.

Before you think the pattern is super-simple, notice that for four rungs, there are five possibilities:
1, 1, 1, 1
1, 1, 2
1, 2, 1
2, 1, 1
2, 2

Warm-up problem: How many possibilities are there for five rungs?

Solution to warm-up:
For five rungs, there are two possible first steps: go to the first rung or to the second. If you go to the first rung, then there are four remaining rungs, giving rise to five possibilities. If you go to the second rung, then there are three remaining rungs. So there are three more possibilities. This gives a total of eight codes.

This reasoning offers a big hint for solving the following problems.

1. How many possibilities are there for the Dren Society¿s eight-rung ladder?

2. How fast could an applicant guarantee to finish, if the judges tell an applicant on his or her first attempt whether the first step was incorrect. (Assume that it takes about a half-minutes to execute one sequence.)