{"code":"tnb","name":"Ấn Nút","description":"Nhân ngày quốc tế thiếu nhi, [user:ami] đã tặng em gái của Flow God *xấu-trai-hơn-ami* một chiếc máy thần kì. Trên chiếc máy là 2 nút màu tím và hồng, cùng 2 số $H$ và $I$. Nếu ấn nút màu tím, số $H$ sẽ tăng 1 đơn vị, nếu ấn nút màu hồng, số $I$ sẽ tăng 1 đơn vị. Flow God ghen tuông vì [user:ami] đã tặng cho em gái cưng của mình một món quà cool ngầu như thế, bèn tìm ra cách để [user:ami] phải mất mặt.\r\n\r\nFlow God *xấu-trai-hơn-ami* muốn [user:ami] ấn các nút tím và hồng tổng cộng không quá F lần. Sau khi thực hiện các thao tác, giả sử 2 số mà [user:ami] nhận được là $N$ và $R$, Flow God muốn $gcd(N,R)$ là lớn nhất có thể. Nhắc lại, $gcd(a,b)$ là một số $c$ lớn nhất mà cả $a$ và $b$ đều chia hết cho $c$ (quy ước $gcd(0, n)=gcd(n, 0)=n$ với mọi số nguyên dương $n$). Tuy nhiên, [user:ami] quá thần thánh, đã tìm ra kết quả siêu nhanh. Flow God tức tối, giận [user:cuom1999] chém ma. \"ma\" ở đây chính là các bạn tham gia contest. \r\n\r\nCác bạn cần trả lời $q$ câu hỏi của Flow God, mỗi câu hỏi có dạng **$H$ $I$ $F$**. Cần in ra $gcd(N,R)$ lớn nhất, $N$ và $R$ là các số nhận được, sau khi ấn hai nút tím và hồng không quá $F$ lần.\r\n\r\n#### Input\r\n\r\n- Dòng đầu tiên chứa một số nguyên dương $q$ là số câu hỏi của Flow God *xấu-trai-hơn-ami*.\r\n- Tiếp theo là $q$ dòng, mỗi dòng chứa một bộ số nguyên không âm **$H$ $I$ $F$** là một câu hỏi.\r\n\r\n#### Output \r\n\r\n- In ra $q$ dòng, mỗi dòng là một số nguyên là $gcd(N,R)$ lớn nhất có thể đạt được.\r\n\r\nDữ liệu đảm bảo luôn có kết quả.\r\n\r\n#### Constraints\r\n\r\n- $H, I \\leq 10^5$\r\n- $q \\leq 10^2$\r\n- $F \\leq 10^{13}$\r\n\r\n#### Scoring \r\n- Subtask $1$ ($5\\%$ số điểm): $H = 0, I \\leq 10^5, F \\leq 10^{13}, q \\leq 10^2$.\r\n- Subtask $2$ ($20\\%$ số điểm): $H, I \\leq 10^5, q \\leq 10^2, F \\leq 10^{5}$.\r\n- Subtask $3$ ($10\\%$ số điểm): $H, I \\leq 10^5, q \\leq 10^2, F = 0$\r\n- Subtask $4$ ($65\\%$ số điểm): $H, I \\leq 10^5, q \\leq 10^2, F \\leq 10^{13}$\r\n\r\n#### Example\r\n\r\n!!! question \"Test 1\"\r\n    ???+ \"Input\"\r\n        ```sample\r\n        3\r\n        0 1 1\r\n        1 1 2\r\n        2 4 1\r\n        ```\r\n    ???+ success \"Output\"\r\n        ```sample\r\n        2\r\n        2\r\n        2\r\n        ```\r\n    ???+ warning \"Note\"\r\n        Với $0$ $1$, có thể ấn nút hồng $1$ lần để thành $0$ $2$. $Gcd(0,2)$ = $2$. Có thể chứng minh đây là kết quả lớn nhất.\r\n        Với $1$ $1$, có thể ấn nút hồng $1$ lần, nút tím $1$ lần để thành $2$ $2$. $Gcd(2,2)$ = $2$. Có thể chứng minh đây là kết quả lớn nhất.\r\n        Với $2$ $4$, có thể không ấn nút nào. $Gcd(2,4)$ = $2$. Có thể chứng minh đây là kết quả lớn nhất.","points":400.0,"partial":true,"time_limit":1.5,"memory_limit":262144,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}