Điều kiện của một dãy ~a~ hợp lệ là với mỗi hợp số ~a_i~, cần phải tồn tại một số nguyên tố ~a_j~ là ước của ~a_i~ mà ~j < i~. Từ đây ta có ý tưởng phải di chuyển các số nguyên tố lên trước hợp số là bộ của nó.

Ngoài ra ta không thể đảo chỗ 2 thừa số nguyên tố. Do để duy chuyển một ước nguyên tố ~a_j~ lên trước ~a_i~ (khi mà ~j > i~), ta cũng cần phải di chuyển phần tử nguyên tố nằm trong ~a_{i + 1}, a_{i + 1}, \ldots, a_{j - 1}~ lên trước ~a_i~.

Như vậy với subtask 1, ta có thể thực hiện thuật toán sau:

for i := 1 to n do:
  if a[i] is not composite: continue  // duyệt i mà a[i] là hợp số
  for j in 1 to n do:
    if a[j] is not prime: continue    // duyệt j mà a[j] là số nguyên tố
    move a[j] before a[i]
    if a[i] \% a[j] == 0: break        // dừng khi đã có ước nguyên tố phía trước
  end for
end for

Với subtask 2, ta có một vài nhận xét sau:

• Số bước cần duyệt chuyển ~a_j~ lên trước ~a_i~ chỉ phụ thuộc vào số hợp số nằm giữa ~a_j~ và ~a_i~, bởi vì các số nguyên tố nằm giữa ta cũng phải di chuyển lên trước ~a_i~.

  • Để tính số bước di chuyển nhanh, ta có thể tính số hợp số nằm trước vị trí ~i~ với mọi ~i~ và dùng hiệp để tính số bước di chuyển.

• Khi đã thực hiện di chuyển xong ~a_j~, ta có thể đánh dấu toàn bộ bội của ~a_j~ là đã xét, để sau đó ta không cần thực hiện xét nữa.

Quan sát này giúp tối ưu 2 vòng lặp lồng nhau ở phía từ ~O(n^2)~ thành ~O(n\log n)~ khi sử dụng 2 con trỏ và mảng đánh dấu.

use std::io::*;

fn solve(a: Vec<usize>) -> usize {
    let n = a.len() + 1;
    let mut is_prime = vec![true; n + 1];
    for i in 2..=n {
        if is_prime[i] {
            for j in (i * i..=n).step_by(i) {
                is_prime[j] = false;
            }
        }
    }
    let mut target_prime_div = vec![0; n + 1];
    for &i in a.iter() {
        if !is_prime[i] {
            continue;
        }
        for j in (i..=n).step_by(i) {
            if target_prime_div[j] == 0 {
                target_prime_div[j] = i;
            }
        }
    }
    let mut prime_marked = vec![false; n + 1];
    let mut cnt_composite_before = vec![0; n + 1];
    for i in 0..a.len() {
        cnt_composite_before[i + 1] = cnt_composite_before[i] + (!is_prime[a[i]] as usize);
    }

    let mut ans = 0;
    let mut f = 0;
    for i in 0..a.len() {
        if !is_prime[a[i]] {
            continue;
        }
        f = (f..i).skip_while(|&x| prime_marked[target_prime_div[a[x]]]).next().unwrap_or(i);
        ans += cnt_composite_before[i] - cnt_composite_before[f];
        prime_marked[a[i]] = true;
    }

    ans
}

fn main() {
    let mut stdin = stdin().lock();
    let mut writer = BufWriter::new(stdout().lock());
    let mut read_line = || -> String {
        let mut s = String::new();
        stdin.read_line(&mut s).unwrap();
        s
    };
    let parse_usize = |s: &str| s.parse::<usize>().unwrap();

    let n_test = parse_usize(&read_line().trim());
    for _test_case in 1..=n_test {
        let _n = parse_usize(&read_line().trim());
        let a = read_line().trim().split_whitespace().map(parse_usize).collect::<Vec<_>>();

        let ans = solve(a);
        writeln!(writer, "{}", ans).unwrap();
    }
}