Bob và Số Đếm Ma Thuật

Trong một buổi biểu diễn ảo thuật đặc biệt, FullHouse Dev được một ảo thuật gia nổi tiếng giao cho một thử thách độc đáo. Ảo thuật gia này, vốn là một nhà toán học tài ba, muốn kiểm tra khả năng giải quyết vấn đề của nhóm thông qua một bài toán ma thuật. Với tinh thần háo hức, FullHouse Dev đã bắt tay vào phân tích và giải quyết bài toán này.

Bài toán

FullHouse Dev được cung cấp một mảng \(A\) gồm \(N\) số nguyên dương. Nhiệm vụ của họ là làm cho "số đếm ma thuật" của toàn bộ mảng bằng \(1\) bằng cách thực hiện một số phép biến đổi. Số đếm ma thuật của mảng được định nghĩa là ước chung lớn nhất (GCD) của tất cả các số trong mảng.

Trong mỗi phép biến đổi, nhóm được phép chọn một số nguyên \(i\) (1 ≤ i ≤ N) và thay thế \(A[i]\) bằng \(A[i]-1\). Chi phí của phép biến đổi này là \(1\). Tổng chi phí sẽ là tổng của chi phí của tất cả các phép biến đổi đã thực hiện.

FullHouse Dev cần tìm ra tổng chi phí tối thiểu để làm cho số đếm ma thuật của toàn bộ mảng bằng \(1\).

INPUT FORMAT:

• Dòng đầu tiên chứa một số nguyên \(T\), biểu thị số lượng bộ test.
• Đối với mỗi bộ test:
  • Dòng đầu tiên chứa một số nguyên \(N\), biểu thị số lượng phần tử trong mảng \(A\).
  • Dòng thứ hai chứa \(N\) số nguyên cách nhau bởi dấu cách, biểu thị các phần tử của mảng \(A\).

OUTPUT FORMAT:

• Với mỗi bộ test, in ra tổng chi phí tối thiểu để làm cho số đếm ma thuật của toàn bộ mảng bằng \(1\).

Ràng buộc:

• \(1 \leq T \leq 10^5\)
• \(1 \leq N \leq 2 \times 10^5\)
• \(1 \leq A[i] \leq 10^9\)

Ví dụ

INPUT

2
4
3 8 6 12
3
2 4 4

OUTPUT

0
1

Giải thích

• Ở bộ test đầu tiên: Số đếm ma thuật của toàn bộ mảng đã là \(1\), nên không cần thực hiện bất kỳ phép biến đổi nào. Do đó, chi phí là \(0\).
• Ở bộ test thứ hai: Nếu FullHouse Dev áp dụng phép biến đổi trên chỉ số thứ \(1\), mảng cập nhật sẽ là \([1, 4, 4]\) và số đếm ma thuật của nó sẽ là \(1\). Vì vậy, chi phí tối thiểu có thể đạt được là \(1\).

FullHouse Dev đã xuất sắc giải quyết bài toán này, khiến vị ảo thuật gia vô cùng ấn tượng. Nhờ vậy, họ đã được mời tham gia vào một buổi biểu diễn ảo thuật đặc biệt, nơi họ có thể kết hợp kỹ năng lập trình với nghệ thuật ảo thuật.