This problem was kindly created for us by Clive Fraser aka CSFPython -
by his own words, inspired by animation in some shop-window on Christmas. Thanks a lot!
A toy store attracts customers into the store by having spectacular displays of toys in the shop window. The floor manager decided to make these displays even more impressive by installing a series of tracks in the bed of the display so that toys could be moved by an automatic mechanism into new positions. The final arrangement consisted of a number of positions where toys could be placed. Most of the time the display would not be moving but at the end of each minute the mechanism would move the toys into new positions. Each toy would either be moved into a position previously occupied by a different toy or would remain in the same position.
Consider a simple arrangement having 7 positions and 7 toys placed in these positions. We can arbitrarily
number the positions 1, 2, 3, 4, 5, 6, 7. We can represent the movements from these positions by a
sequence of 7 numbers. In this example we will use the sequence 2, 1, 4, 6, 3, 5, 7. We interpret this
movement sequence as follows: All movements take place simultaneously. The toy at position 1
moves to position 2. The toy at position 2 moves to position 1. The toy at position 3 moves to position 4.
Similarly, the toys at positions 4, 5, 6 and 7 move to positions 6, 3, 5 and 7. Notice that
this means that the toy in position 7 will remain in position 7. Let us describe the toys
in positions 1 ... 7 by using the alphabetic letters a ... g. The movements at the end of each minute can
be represented in the following table.
Start position: a, b, c, d, e, f, g
After 1 minute: b, a, e, c, f, d, g
After 2 minutes: a, b, f, e, d, c, g
After 3 minutes: b, a, d, f, c, e, g
After 4 minutes: a, b, c, d, e, f, g
It can be seen that, after 4 minutes, all of the toys have returned to their original positions.
For any arrangement of toys and positions, using this kind of mechanism, the toys will always return to their
original position after a certain number of minutes. For complex arrangements the number of minutes can be
quite large.
In this problem you will be given a movement sequence for a number (S) of starting positions. For S starting
positions the positions will be numbered from 1 to S inclusive. You have to find the number of minutes
before all of the toys first return to their original positions. None of the problems will have more than 750
positions.
The first line of the problem will be a single integer N denoting the number of test cases.
Each test case will consist of two lines. The first line contains a single integer S, the number of positions
(and toys) in the display. The second line contains a sequence of S space-separated integers. This is the
movement sequence for the display. For each test case you must find the number of minutes before all of the
toys first return to their original positions. Give these answers, separated by spaces, as a single string.
Example:
input:
3
7
2 1 4 6 3 5 7
15
9 15 4 13 10 12 14 3 8 5 6 7 1 2 11
103
89 102 94 86 66 46 11 55 79 71 48 103 15 5 78 1 35 41 65 17 28 101 24 57 99 2 23 36 85 40 62 31 72 9 47 25
16 29 75 95 32 13 61 38 26 3 34 52 100 37 12 43 88 98 56 87 82 44 4 90 93 20 83 74 73 92 81 97 49 58 70
64 63 69 6 14 27 19 80 33 54 50 30 10 96 7 18 68 84 53 76 60 59 45 67 39 42 91 77 51 21 22 8
answer:
4 42 71820
Note: the last line of the input is split into three (with indents) - but it is just for convenience of representation. Real input never has lines split however long they could be!