Chia Số

Xem PDF

Điểm: 350 Thời gian: 2.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Đứ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.

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.

Input

  • Dòng đầu tiên chứa \(t\) là số câu hỏi.
  • \(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\).

Output

  • 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.

Scoring

Trong tất cả các test, \(1 \leq c,u,o,m \leq 10^{18}\)

  • Subtask \(1\) (\(40\%\) số điểm): \(t=1, u=o=m\)
  • Subtask \(2\) (\(20\%\) số điểm): \(t \leq 100\), \(u,o,m\) đôi một nguyên tố cùng nhau
  • Subtask \(3\) (\(20\%\) số điểm): \(t \leq 100, u=o\)
  • Subtask \(4\) (\(20\%\) số điểm): \(t \leq 100\)

Example

Test 1

Input
3
6
1 2 3
7
1 2 7
8
4 4 4
Output
2
1
-1
Note

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.
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.


Bình luận


  • 1
    longkold00 2:54 p.m. 12 Tháng 10, 2021

    bài này các bạn hoàn toàn có thể sử dụng đệ quy để giải bài toán theo cách đơn giản nhé :v, ai đã biết đệ quy có thể tham khảo phần đệ quy của mình :V


    hehe


    • -6
      conong11111 8:07 a.m. 16 Tháng 1, 2021

      Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.


      • -14
        ekhoavvdd 6:34 p.m. 7 Tháng 1, 2021 đã chỉnh sửa

        Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.