BT nhận được món quà sinh nhật thú vị. Đó là một dãy số nguyên dương. Anh ta quyết định biến đổi dãy số nhận được thành dãy toàn số 1. Tại mỗi bước, anh ta chọn ra một tập hợp các số có cùng một ước số là số nguyên tố p nào đó, chia tất cả các số trong tập hợp này cho số p. Hỏi rằng BT phải thực hiện tối thiểu bao nhiêu bước biến đổi để thu được dãy toàn số 1?

Input:

• Dòng đầu tiên ghi số nguyên dương T là số bộ dữ liệu. Tiếp theo là T nhóm dòng, mỗi nhóm dòng mô tả một bộ dữ liệu theo qui cách sau:
• Dòng đầu tiên ghi số nguyên dương N - số lượng số của dãy số
• Dòng thứ hai chứa N số nguyên ~a_1~,~a_2~,…,~a_N~ - dãy số được cho.

Output:

• Với mỗi bộ dữ liệu in ra trên một dòng số nguyên - số lượng tối thiểu các bước cần thực hiện đe thu được dãy chỉ chứa toàn số 1.

Example:

Input

1
3
1 2 4

Output

2

Subtaks:

T = 5; 2 ≤ N ≤~10^5~; 1 ≤ ~a_i~ ≤ 3         [10%]
T = 3; 1 ≤ N ≤ 10;1 ≤ ~a_i~ ≤ ~10^6~        [40%]
T = 3; 1 ≤ N ≤ ~10^5~;1 ≤ ~a_i~ ≤ ~10^6~    [50%]