There is a robot located in the cell ((a,b)) of an infinite grid. Misha wants to move it to the cell ((0,0)). To do this, he has fixed some integer (k). Misha can perform the following operation: choose two integers (dx) and (dy) (both from (0) to (k) inclusive) and move the robot (dx) cells to the left (in the direction of decreasing (x) coordinate) and (dy) cells down (in the direction of decreasing (y) coordinate). In other words, move the robot from ((x,y)) to ((x - dx, y - dy)). The cost of the operation is: (1), if the chosen pair ((dx,dy)) is used for the first time; (0), if the pair ((dx,dy)) has been chosen before. Note that if (dx \ne dy), the pairs ((dx, dy)) and ((dy, dx)) are considered different. Help Misha bring the robot to the cell ((0,0)) with minimum total cost. Note that you don't have to minimize the number of operations. The first line contains a single integer (t) ((1 \le t \le 10^4)) — the number of test cases. The only line of each test case contains three integers (a, b), and (k) ((1 \le a, b, k \le 10^{18})). For each test case, output a single integer — the minimum total cost of operations required to move the robot to the cell ((0,0)). In the first test case, the operation ((3,5)) can be applied once. The robot will immediately go to ((0,0)), and the cost of the operation will be (1). In the second test case, the operations: ((1,1)), ((0,1)), and ((1,1)) can be applied. After the first operation, the robot will be at cell ((1,2)), after the second one — at ((1,1)), and after the third one — at ((0,0)). The cost of the first and second operations is (1), while the third is (0), as the pair ((1,1)) has already been used in the first operation. In the third test case, the pair ((4,6)) can be chosen three times in a row. In the fourth test case, the operations: ((4,2)) a