Polycarp found on the street an array a of n elements.

Polycarp invented his criterion for the beauty of an array. He calls an array a beautiful if at least one of the following conditions must be met for each different pair of indices i ≠ j: 

  * a_i is divisible by a_j; 
  * or a_j is divisible by a_i. 



For example, if: 

  * n=5 and a=[7, 9, 3, 14, 63], then the a array is not beautiful (for i=4 and j=2, none of the conditions above is met); 
  * n=3 and a=[2, 14, 42], then the a array is beautiful; 
  * n=4 and a=[45, 9, 3, 18], then the a array is not beautiful (for i=1 and j=4 none of the conditions above is met); 



Ugly arrays upset Polycarp, so he wants to remove some elements from the array a so that it becomes beautiful. Help Polycarp determine the smallest number of elements to remove to make the array a beautiful.

Input

The first line contains one integer t (1 ≤ t ≤ 10) — the number of test cases. Then t test cases follow.

The first line of each test case contains one integer n (1 ≤ n ≤ 2 ⋅ 10^5) — the length of the array a.

The second line of each test case contains n numbers a_1, a_2, …, a_n (1 ≤ a_i ≤ 2 ⋅ 10^5) — elements of the array a.

Output

For each test case output one integer — the minimum number of elements that must be removed to make the array a beautiful.

Example

Input


4
5
7 9 3 14 63
3
2 14 42
4
45 9 3 18
3
2 2 8


Output


2
0
1
0

Note

In the first test case, removing 7 and 14 will make array a beautiful.

In the second test case, the array a is already beautiful.

In the third test case, removing one of the elements 45 or 18 will make the array a beautiful.

In the fourth test case, the array a is beautiful.
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+7;
int dp[N];
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        vector<int> v(n);
        map<int,int> mp;
        for(int i=0;i<n;i++){
            cin>>v[i];
            mp[v[i]]++;
        }
        sort(v.begin(),v.end());
        for(int i=v.size()-1;i>=0;){
            dp[v[i]]=mp[v[i]];
            for(int j=2*v[i];j<N;j+=v[i]){
                 dp[v[i]]=max(dp[j]+mp[v[i]],dp[v[i]]);
            }
            i=i-mp[v[i]];
        }
        int mx=0;
        for(int i=0;i<N;i++){
              mx=max(mx,dp[i]);
        }
        cout<<n-mx<<endl;
        for(int i=0;i<=v[n-1];i++){
            dp[i]=0;
        }
    }
    return 0;
}