← 返回题目列表

Codeforces · 1720/D1

D1. 异或子序列(简单版)

中文机器翻译题面 查看原题

这是问题的简单版本。唯一的区别是在这个版本中$$$a_i \le 200$$$。

给你一个 $$$n$$$ 整数数组 $$$a_0, a_1, a_2, \ldots a_{n - 1}$$$。 Bryap 想要找到数组中最长的美丽子序列。

数组 $$$b = [b_0, b_1, \ldots, b_{m-1}]$$$,其中 $$$0 \le b_0 < b_1 < \ldots < b_{m - 1} < n$$$ 是数组 $$$a$$$ 的长度 $$$m$$$ 的子序列。

如果满足以下条件,则长度为 $$$m$$$ 的子序列 $$$b = [b_0, b_1, \ldots, b_{m-1}]$$$ 被称为美丽的:

- 对于任何 $$$p$$$ ($$$0 \le p < m - 1$$$) 成立:$$$a_{b_p} \oplus b_{p+1} < a_{b_{p+1}} \oplus b_p$$$。

这里 $$$a \oplus b$$$ 表示 $$$a$$$ 和 $$$b$$$ 的按位异或。例如,$$$2 \oplus 4 = 6$$$ 和 $$$3 \oplus 1=2$$$。

Bryap 是一个简单的人,所以他只想知道最长的子序列的长度。帮助 Bryap 找到他问题的答案。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^5$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \leq n \leq 3 \cdot 10^5$$$) — 数组的长度。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_0,a_1,...,a_{n-1}$$$ ($$$0 \leq a_i \leq 200$$$) — 数组的元素。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$3 \cdot 10^5$$$。

输出

对于每个测试用例,打印一个整数——最长的美丽子序列的长度。

示例

输入 #1

3
2
1 2
5
5 2 4 3 1
10
3 8 8 2 9 1 6 2 8 3

输出 #1

2
3
6

注意

在第一个测试用例中,我们可以选择整个数组作为一个漂亮的子序列,因为 $$$1 \oplus 1 < 2 \oplus 0$$$。

在第二个测试用例中,我们可以选择索引为 $$$1$$$、$$$2$$$ 和 $$$4$$$ 的元素(在 $$$0$$$ 索引中)。对于此元素,成立:$$$2 \oplus 2 < 4 \oplus 1$$$ 和 $$$4 \oplus 4 < 1 \oplus 2$$$。