bool isprime(int n)
{
    for(int i=2;i<(n/2)+1;i++)
    {
        if(n%i == 0)
        {
            return false;
        }
    }
    return true;
}
vector<int> waiter(vector<int> number, int q) 
{
    vector<int> p,a,b,res;
    vector<int> temp;
    int x;
    for(int i=2;i<10000;i++)
    {
        if(isprime(i))
        {
            p.push_back(i);
        }
    }    
    
    for(int i=0;i<q;i++)
    {
        int size = number.size();
        for(int j=0;j<size;j++)
        {
            x = number.back();
            
            if(x%p[i] == 0)
            {
                b.push_back(x);
                number.pop_back();
            }
            else
            {
                a.push_back(x);
                number.pop_back();
            }
        }
        number = a;
        a.clear();
        while(!b.empty())
        {
            res.push_back(b.back());
            b.pop_back();
        } 
    }
    while(!number.empty())
    {
        res.push_back(number.back());
        number.pop_back();
    }
    return res;
}

def get_primes_till_N(N):
    """
    Creates an array of primes till N.
    """
    if N < 2:
        return []
    
    # Initialize a list to track prime numbers
    is_prime = [True] * (N + 1)
    is_prime[0], is_prime[1] = False, False  # 0 and 1 are not primes
    
    # Apply the Sieve of Eratosthenes algorithm
    for start in range(2, int(N**0.5) + 1):
        if is_prime[start]:
            for multiple in range(start*start, N + 1, start):
                is_prime[multiple] = False
    
    # Collect all prime numbers into a list
    primes = [num for num, prime in enumerate(is_prime) if prime]
    
    return primes

# Create array of primes till 10001:
primes = get_primes_till_N(10001)

def waiter(number, q):
    answers = list()
    A = number[:]

    for i in range(q):
        # Finish iteration if A is empty
        if not A:
            break
        # Store values in pile B
        B = [num for num in A if num % primes[i] == 0][::-1]
        # Remove values from pile A
        A = [num for num in A if num % primes[i] != 0][::-1]
        # Add values of pile B to answers:
        answers += B[::-1]
        
    return answers + A[::-1]

def is_prime(num):
    if num < 2:
        return False
    for i in range(2, int(num**0.5) + 1):
        if num % i == 0:
            return False
    return True

def first_n_primes(n):
    primes = []
    num = 2
    while len(primes) < n:
        if is_prime(num):
            primes.append(num)
        num += 1
    return primes


def waiter(number, q):
    primes = first_n_primes(q)
    answers = []
    arr = number
    for p in primes:
        B=[]
        A =[]
        for e in arr:
            if e % p == 0:
                B.append(e)
            else:
                A.append(e)
        answers+=B
        arr = A[::-1]
    answers +=A
    return answers

def waiter(number, q):
    # Write your code here
    answer = []
    
    point = 0
    index = 2
    
    while point < q:
        check = 0
        for now in range(1, index + 1):
            if index % now == 0:
                check += 1
            if now < index and check == 2:
                break
            if check == 2:
                point += 1
                
                A = []
                B = []
                
                for i in range(len(number)):
                    if number[i] % index == 0:
                        A.append(number[i])
                    else:
                        B.append(number[i])
                if point < q:
                    B.reverse()
                number = B
                answer.extend(A)
        index += 1
     
    answer.extend(number)
    return answer