On a distant planet of dreams, Toilet-Ares is packing up the things and memories, ready to commerce a new adventurous road trip. With outstanding driving skills, the driving route may be a segment, a curve, a polyline, and it can be closed (end-to-end), even self-intersect, as long as the route is continuous. The fuel capacity, oddly enough, can support km driving. Thus, the route has a maximum total length of km.

The planet's surface is expansive and flat enough to regard as a plane. A Cartesian coordinate system, formed with longitude and latitude, is used to describe each geographical position on the planet. Every  km, draw a line of points with some equal longitude, named meridian. Similarly, every  km, draw a line of points with some equal latitude, named parallel. Notice that innumerous meridians are perpendicular to innumerous parallels, constructing a grid called graticule, dividing the plane into infinite cells. Inhabitants there are used to defining those cells as regions, and to avoid conflict, positions on meridians or parallels belong to no region.

There are so many different kinds of landscapes to see, to admire, to experience. Toilet-Ares starts the drive at an arbitrary position on the planet. Whenever passing a region for the first time, Toilet-Ares will remember its visual feature (which is always distinguishable from any other region). So, it will be easy for Toilet-Ares to count up the number of regions visited as the road trip ends.

For example, in both situations shown below, four different regions are visited along the route.

Just as the saying goes, "Where there is a will, there is a way." Toilet-Ares always attempts to figure out how many different regions at most can visit in the whole road trip. And you, as a friend, are here to answer this question.

The input contains multiple test cases. The first line of input contains one integer  ().

In the following  lines, each line contains two real numbers  (), describing one test case. Any of them may be an integer or contains at most 8 decimal digits. It is guaranteed that there is no trailing zero in decimal place.

For each test case, output the corresponding answer with an integer in one line.

2
5 5
1.5 1.5

4
8