This problem was created by Clive Fraser - thanks a lot!
Alan and Bob are addicted to gambling although they have sufficient sense to keep the stakes fairly small.
Many of their gambling games are based on die throws since this can be done anywhere and only requires that one
of them has a die in their pocket. Alan and Bob always use high quality dice so that each of the outcomes
1, 2, 3, 4, 5 and 6 is equally probable. One game that they play fairly often is to bet on a 6
appearing within 4 successive die throws or on no 6s appearing in a run of 8 successive die throws.
Alan and Bob are always looking for new ways of setting up their games. Alan suggested that it might be
interesting to look for a specific sequence of numbers in a set of die throws, rather than for just a single
number. For example, Alan suggested that they might look for the specific sequence 5151. The immediate problem
is that neither Alan nor Bob have any idea of how likely such a sequence is to appear. What they want to know is
the average number of die throws (over a very large number of trials) before the sequence 5151 first appears.
More formally, this is the expectation value of the number of die throws before the sequence 5151 first
appears. It is possible (but very unlikely) that the first 4 die throws (in order) could be 5, 1, 5, 1.
Clearly 4 is the minimum number of throws which could produce the sequence. Another sequence of throws ending
in 5151 is 6, 3, 5, 1, 5, 3, 3, 4, 1, 2, 2, 5, 1, 5, 1. This is a sequence of
15 die throws. We stop as soon as the sequence 5151 appears. Clearly this must appear as the last 4 throws of
the sequence of die throws. 15 throws is more than the previous 4 throws but is still much smaller than the
expected number of throws to obtain this result. It is easy to create a simple simulation to carry out a large
number of trials. This will confirm that the expected number of throws to obtain the sequence 5151 (rounded
to the nearest integer) is 1332.
In this problem you will be given a number of sequences. Each of these is made up of numbers in the range 1 to 6
representing a sequence generated by successive die throws. In each case you need to find the expectation number
of die throws needed to generate this sequence. All answers are to be rounded to the nearest integer. The length
of the number sequence will not exceed 19.
The first line of the problem will be a single integer N denoting the number of test cases. Each test case will
consist of a single string of numbers which is the target sequence. For each test case you must find the expected
number of die throws needed to generate this target sequence. Give these answers (as integers), separated by
spaces, as a single string.
Example:
input:
3
5151
22122
1551551
answer:
1332 7818 281238