Experienced participants of the Ural Championship come to Yekaterinburg in advance to get accustomed to the severe weather conditions, walk around the city, and, of course, visit the “Limpopo” Water Park. Not many people know that there is Plant No. 404 near the water park, and this plant is called “Error 404” by the locals. The plant is not easy to find indeed, and it is still more difficult to learn what is happening there. Fortunately, one can watch the plant from a nearby pedestrian bridge. Because of the seeming stillness and desolation of the plant, one may think that it is out of operation, but this is not so. The main work area of the plant is the repair of aviation engines.
Some time ago the plant received an order to repair a broken gas turbine engine. It turned out that some blades were torn off, which resulted in an excess load on the engine shaft. Experts at the plant have decided that the engine could be repaired quickly by removing some of the intact blades so that the center of masses of the remaining blades would be on the rotation axis once again. To keep the engine power as large as possible, a minimum number of blades should be removed. At least one blade must be left, otherwise the engine would not work at all. The experts assert that when all the blades were intact their endpoints formed a regular n-gon. Tell them how many blades will be kept.
The first line contains an integer T<=100 indicating the total number of test cases.
For each test case, the first line contains the initial number of blades in the turbine n and the number of torn blades k (3 ≤ n ≤ 20000; 1 ≤ k ≤ n − 1). The integer n has at most two distinct prime divisors. The next line contains k integers, which are the numbers of the torn blades in ascending order. The blades are numbered from 1 to n clockwise.
For each test case please output a line containing the maximum number of blades that would be reserved. If it is impossible to repair the engine by removing some of the blades, output “−1”.
2 12 3 3 4 12 3 1 1
7 -1
Migrated from old NTUJ.
Ural 1765
No. | Testdata Range | Score |
---|