Walking the Dog

You have a labrador that becomes lazy and gains weight unless it gets enough exercise, so you often take it for walks in a local park.

You already get enough exercise yourself and do not want to run after the dog, so you bought a very long rope and tied one end to the dog. Assume the rope has infinite length. You sit at a comfortable point while holding the other end and let the dog run freely. As the dog moves through the park, the rope may wind around the flagpole standing at the center. You allow this, and whenever the rope passes over the place where you are sitting, you jump over it so that you do not get tangled.

Given the points that the dog visits in order, determine how many complete times the rope is wrapped around the flagpole after the walk finishes. Round the answer down to an integer. The dog always takes the shortest path to the next point. If that path goes exactly through the flagpole, the dog goes around it counterclockwise.

The park is represented by a coordinate plane with -10^9 <= x, y <= 10^9. The flagpole is at (0, 0).

The first line contains an integer n (0 < n <= 10000), the number of test cases.

For each test case:

• The first line contains an integer m (0 < m <= 1000), the number of points in the dog's walk.
• Each of the next m lines contains two integers x_i and y_i (-10^9 <= x_i, y_i <= 10^9, (x_i, y_i) != (0, 0)), the coordinates of the i-th point the dog runs to.

For each test case, print one line containing one integer: the number of complete windings the rope has made around the flagpole after you sit at (x_1, y_1) and let the dog walk through (x_1, y_1) -> (x_2, y_2) -> ... -> (x_m, y_m).