Trucks có ~N~ cái hộp được đánh số từ ~1~ đến ~N~, mỗi hộp chứa một số quả bóng.

Anh muốn thêm bóng vào một vài hộp để số lượng bóng trong ~N~ hộp tạo thành một dãy số không giảm và ước chung lớn nhất của chúng lớn hơn ~1~.

Tính số lượng quả bóng ít nhất cần thêm.

Input

• Dòng đầu tiên chứa số nguyên dương ~Q~ là số lượng truy vấn ~(1 \le Q \le 10)~.

• Trong ~Q~ nhóm dòng tiếp theo:

  • Dòng đầu tiên chứa số nguyên dương ~N~ ~(1 \le N \le 10^4)~.

  • Dòng thứ hai chứa ~N~ số nguyên dương biểu diễn số lượng bóng trong ~N~ hộp, các số này không vượt quá ~10^4~.

Output

Gồm ~Q~ dòng, dòng ~i~ là kết quả của truy vấn thứ ~i~.

Sample Input 1

1
3
1 2 5

Sample Output 1

2