森友会里打音游
题号：NC296389
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

2025 年 1 月，PJSK 日服开放 MySEKAI 板块，由于其场景设计和游玩方法与任天堂某著名养成系游戏相似，所以玩家称该板块为「烤森」或「烤友会」。
        你的背包有 n 个物件，现在你按顺序依次将它们放在了草坪上，从左到右第 i 个物品的大小为 a_i。
        现在你可以移除一些物件（也允许不移除），请问你最多可以保留多少个物件，使得剩下的物件中，对于任意相邻的两个物件，二者大小均有整除关系？（如果只剩一个物件默认符合条件）
        在此，我们称两个正整数 a,b 有「整除关系」，当且仅当 a \mid b 或 b \mid a 成立，即 a 是 b 的约数或 a 是 b 的倍数。

输入描述:

    每个测试文件均包含多组测试数据。第一行输入一个整数 T \left(1 \le T \le 10^4\right) 代表数据组数，每组测试数据描述如下：
    第一行，输入一个整数 n \ (1 \le n \le 2 \times 10^5) 代表物件数量。
    第二行，输入 n 个整数 a_1,a_2,...,a_n \ (1 \le a_i \le n) 代表每个物件的大小。
    对于同一个测试点，保证所有数据的 n 之和不超过 2 \times 10^5。

输出描述:

    对于每组数据，输出一行一个正整数，代表最多可以保留的物件数。
示例1

输入

复制 
2
6
1 1 4 5 1 4
16
13 3 10 15 5 10 11 14 10 13 15 12 2 1 3 2

输出

复制 
5
8

说明

    对于第一组数据，把 5 删去，剩余的 1,1,4,1,4 就可以满足条件。可以证明没有比它更优的方案，因此输出 5。