CF2125B Left and Down

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) $ and $ (5,5) $ can be applied.