{"code":"kh03","name":"number of steps","description":"Bạn được cho 2 số nguyên $a, b$.\r\n\r\nHãy làm việc này sau đây cho đến khi một trong hai số $a, b$ là số 0 :\r\n\r\n- Nếu $b \\leq a$ thì lấy a trừ đi b $(a = a - b)$.\r\n- ngươc lại lấy b trừ a$(b = b - a)$.\r\n\r\nNhập vào 2 số $a, b$. Hãy đếm số lần bạn làm công việc trên\r\n\r\n

Input

\r\n\r\n- $t (t \\leq 1000)$ - số test\r\n- $t$ dòng, mỗi dòng gồm 2 số nguyên dương $a, b (a, b \\leq 1000000000)$\r\n\r\n

Output

\r\n\r\n- $t$ dòng, số lần thực hiện để một trong 2 số $a, b$ có 1 số là số 0\r\n\r\n

Example

\r\n\r\n!!! question \"Test 1\"\r\n\r\n ???+ \"Input\"\r\n\r\n ```sample\r\n 1\r\n 4 17\r\n ```\r\n\r\n ???+ success \"Output\"\r\n\r\n ```sample\r\n 8\r\n ```\r\n \r\n ??? warning \"Note\"\r\n\r\n $(4\\ 17) \\rightarrow (4\\ 13) \\rightarrow (4\\ 9) \\rightarrow (4\\ 5) \\rightarrow (4\\ 1) \\rightarrow (3\\ 1) \\rightarrow (2\\ 1) \\rightarrow (1\\ 1) \\rightarrow (0\\ 1)$","points":100.0,"partial":false,"time_limit":0.3,"memory_limit":655360,"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}}