DWITE, December 2011, Problem 2

In the mountainous city of Dwitia, there is said to be ~N~ magical ponds. Any object that touches any of these ponds is said to multiply some fixed number of times! Wanting to test this theory out, Tony makes a perilous trip to these ponds with some number of apples. He places the apples on the first pond, waits for the number of apples to multiply, then takes some portion of these apples from the first pond and places them on the second pond, waits for the number of apples to multiply again, and takes some from the second pond and places them on the third pond, and so on. When he places the apples on the final pond, he realized something remarkable: all the ponds now have the same number of apples! Given how much each pond multiplies the number of apples by, determine the smallest number of apples Tony could have started with.

The input will contain 5 test cases. The first line of each case is an integer ~1 \le N \le 8~, the number of magical ponds in Dwitia. The following line has ~N~ space separated integers ~1 \le M \le 10~, the number apples would multiply by in each of the ponds. Ponds with ~M~ value of ~1~ are not very magical.

The output will contain 5 lines of output, the minimal number (at least ~1~; trivial answer of ~0~ is just too easy and doesn't test for "magicality") of apples Tony could have started with, such that all ponds end up with the same number of apples at the end.

About first sample input: Starting with ~7~ apples, the first pond turns them into ~14~. Tony takes ~6~ (~8~ are left in the pond). The second pond turns those ~6~ into ~12~. Tony takes ~4~ (~8~ are left in the pond). The third pond turns those ~4~ into ~8~. At this point, all ~3~ ponds have the same number of apples.

About second sample input: while the pond produces a lot of copies, there is only one of them, so starting with any number would make "all ponds have the same number of apples". Since we are looking for the smallest number that is at least one, ~1~ is the answer.

Sample Input

3
2 2 2
1
10

Sample Output

7
1

Problem Resource: DWITE