Your team will have an important mission after the contest: You have to set up a new playground for a couple of the beloved pets of Code Fem: two extremely cute guinea pigs. For that reason, your team needs to buy decorative lights of different colors to embellish the place. Each light is only one color.
The decorative lights are distributed all over the surface where the playground is to be built by your mates; however, you had to go to the bathroom and did not get to know the arrangement of the lights. Your peers have noticed that they could join the lights with imaginary straight lines and create polygons whose vertices are those lights themselves. After thinking a lot about the topic, they came up with a question that challenged you to solve: Regardless of the arrangement they chose, and the colors of lights they utilized, how many vertices does the largest polygon that you can guarantee have, such that all the vertices (lights) are the same color? It does not matter what color it is.
In this case, consider that the more vertices a polygon has, the greater it is, regardless of its area. Moreover, the polygon could be convex or non-convex. You can be sure there are no three collinear lights.
The first line will contain a natural number $$$1 \leq T \leq 1000$$$: the number of input cases. Then, you will receive $$$T$$$ lines, each with two positive integers $$$n$$$ and $$$k$$$, where $$$n$$$ ($$$ 3 \leq n \leq 10^{15} $$$) is the number of spots where a light is to be set up, and $$$k$$$ ($$$ 1 \leq k \leq 10^{15} $$$) is the number of available colors for the lights.
For each case, print on a different line the number of vertices that the greatest polygon has. If the figure is not a polygon, print 0.
2 10 3 7 4
4 0
| Name |
|---|


