Author: | Антон Карабанов | Time limit: | 1 sec | |
Input file: | Standard input | Memory limit: | 512 Mb | |
Output file: | Standard output |
Children theme park has opened a new attraction "Karousel" for n persons. According to safety regulations, when the attraction is running, children must be seated so that the center of mass of all riders coincides with the center of carousel and the distances between them alongside the circumference is equal. For example, for n = 6, 2, 3 or 6 children may ride simultaneously, while for n = 5 — only exactly 5. In other words, attraction is allowed to start if it has k children, where k — is a divisor of n and k ≠ 1.
There are d children waiting in the queue for the carousel. After finishing the ride children leave to other attractions. What is the minimum number of runs to let all children ride the carousel once each?
Two lines of input contain integers n and d.
Output a single integer — answer to the problem. If it is impossible for all children to get a ride, output -1.
1 ≤ (d, n) ≤ 105
In the first sample n = 16 and d = 14 (16 seats on carousel, 14 children in the queue). It is enough to run carousel 3 times: first time for 8 children, second — for 4, third — for 2.
In the first sample n = 15 and d = 7. It is impossible to let all children ride since according to regulations only 3, 5 or 15 are allowed to ride at a time.
No. | Standard input | Standard output |
---|---|---|
1 |
|
|
2 |
|
|