408046: GYM102966 J Just Turn the Wheels!

Polygonia (a country where everything has to be a polygon) has a scientific conflict, the progressive side, that wants to legalize circles against the conservatives, that want to keep circles illegal in order to keep their traditions.

In order to proof their advantage, the circle lovers have design a motorbyke that use circular-shaped wheels, as an attempt to replace the polygon-shaped ones, but in order to disguise the circle-ban, they have painted the wheels as if they have a regular polygon. You can see an example of them in the next image.

The motorbike has always two wheels, but in some cases, they do not represent the same polygon, for example, the front wheel is square-shaped and the back one is hexagon-shaped. In order to keep the disguise, the motorbike has to stop exactly when both wheels have one side of the polygon parallel to the ground (so it seems that it is a polygon-shaped wheel).

It is guaranteed that both wheels, despite having different polygons, are the same size. A turn is the energy needed to roll a wheel 30 degrees, it is always the same, regardless the wheel's size. It is safe to assume that when one wheel is rolled by $$$x$$$ angle, the other one, moves $$$x$$$ angle too.

So, given the wheel's circumference, the number of the simulated sides of the back and the front wheel, and a distance (in the same unit as the circumference), your task is to compute the minimum integer number of turns that are necessary to cover that distance and that guarantees that in both wheels, there is one side parallel to the ground. When the bike starts its journey, this condition is guaranteed.

The input consist on an integer number $$$T$$$ ($$$1\leq T \leq 10^5$$$) that denotates the number of test cases. The next $$$T$$$ lines have four positive integer numbers separated by space:

• $$$C$$$ ($$$1\leq C \leq 10^3$$$) The circunference of the wheel.
• $$$F$$$ ($$$3\leq F \leq 233$$$) The number of sides of the front wheel.
• $$$B$$$ ($$$3\leq B \leq 233$$$) The number of sides of the back wheel.
• $$$S$$$ ($$$1\leq S \leq 10^9$$$) The distance that must be covered by a bike's journey.

For each test case, print on a single line an integer that represents the minimum number of turns required.

1
2 8 4 10

60