Orac 与模型

• 时间限制：3 秒
• 内存限制：256 MiB

题目描述

给出一个长度为 $n$ 的序列 $a$，并令 $s$ 为 $a$ 的子序列，$pos_i$ 为 $s_i$ 在原序列里的位置
当且仅当 $s_j<s_{j+1}$ 且 $pos_j \mid pos_{j+1}$ 时，序列 $s$ 是美丽的

你需要求出序列 $a$ 的最长的美丽子序列的长度

输入格式

本题有多组数据

第一行一个整数 $T$，表示数据组数
对于每组数据，第一行一个整数 $n$，表示序列的长度
第二行 $n$ 个整数，表示序列 $a$

输出格式

对于每组数据，输出一行一个整数，表示最长美丽子序列的长度

样例输入 1

4
4
5 3 4 6
7
1 4 2 3 6 4 9
5
5 4 3 2 1
1
9

样例输出 1

2
3
1
1

数据范围

对于所有数据，$1\le T\le 100$，$1\le n\le 10^5$，$1\le a_i\le 10^9$；所有测试用例中 $n$ 的总和不超过 $10^5$。