{"code":"dividing","name":"Chia Số","description":"Đức rất thích cống. Nhận thấy sở thích này rất bất thường và không sạch sẽ, **ami** quyết định bày Đức một trò chơi liên quan đến số học.\r\n\r\n**ami** cho Đức 4 số $c,u,o,m$. Đức có thể chọn một trong 3 số $u, o, m$ và chia $c$ cho số được chọn. Đức có thể lặp lại thao tác trên với số lần vô hạn nếu cậu thích, mục tiêu là làm cho số $c$ trở thành $1$. Tuy không thích số học, nhưng lại không dám làm trái lời **ami**, Đức muốn nhờ các bạn tìm ra số thao tác ít nhất để biến $c$ thành $1$, hoặc báo cho Đức là không thể, để Đức còn có thời gian đi chơi với cống.\r\n\r\n####Input\r\n- Dòng đầu tiên chứa $t$ là số câu hỏi.\r\n- $t$ câu hỏi có dạng như sau: Dòng đầu tiên của mỗi câu hỏi chứa 1 số nguyên $c$, dòng thứ hai chứa 3 số nguyên $u, o, m$.\r\n\r\n####Output\r\n- Với mỗi câu hỏi, hãy in ra số thao tác ít nhất cần dùng để biến $c$ thành $1$ hoặc in ra $−1$ nếu không tồn tại bất kì cách làm nào.\r\n\r\n####Scoring\r\nTrong tất cả các test, $1 \\leq c,u,o,m \\leq 10^{18}$\r\n- Subtask $1$ ($40\\%$ số điểm): $t=1, u=o=m$\r\n- Subtask $2$ ($20\\%$ số điểm): $t \\leq 100$, $u,o,m$ đôi một nguyên tố cùng nhau\r\n- Subtask $3$ ($20\\%$ số điểm): $t \\leq 100, u=o$\r\n- Subtask $4$ ($20\\%$ số điểm): $t \\leq 100$\r\n\r\n####Example\r\n\r\n!!! question \"Test 1\"\r\n    ???+ \"Input\"\r\n        ```sample\r\n        3\r\n        6\r\n        1 2 3\r\n        7\r\n        1 2 7\r\n        8\r\n        4 4 4\r\n        ```\r\n    ???+ success \"Output\"\r\n        ```sample\r\n        2\r\n        1\r\n        -1\r\n        ```\r\n    ??? warning \"Note\"\r\n        Với $c=6,u=1,o=2,m=3$, ta có thể lấy $6/3/2=1$ hoặc $6/2/3=1$. Tổng cộng cần ít nhất 2 thao tác.\r\n        Với $c=7,u=1,o=2,m=7$, ta có thể lấy $7/7=1$. Tổng cộng cần ít nhất 1 thao tác.","points":350.0,"partial":false,"time_limit":2.0,"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}}