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

3
6
1 2 3
7
1 2 7
8
4 4 4

2
1
-1