1241 : 二合一

Description

这是一道二合一题。

给定一个长度为 \(n\) 的颜色序列 \(c_1,\cdots, c_n (1 \le c_i \le n)\)。

对于 \(1 \le x \le n, 1 \le l \le r \le n\)，定义 \(\operatorname{occ}(x,l,r)\) 为颜色 \(x\) 在序列 \(c\) 的第 \(l\) 至 \(r\) 项出现的次数。

你需要找到序列的一个区间 \([l,r]\)，再找到两种颜色 \(x,y\)（注意 \(x,y\) 可以相等），使得 \[\operatorname{occ}(x,l,r) \mathop{\mathrm{or}} \operatorname{occ}(y,l,r)\] 最大，其中 \(\mathrm{or}\) 为二进制按位或。你只需要输出这个最大值。

Input

本题有多组测试数据。第一行一个正整数 \(T\)（\(1\leq T\leq 10^5\)） 表示数据组数。对于每组数据，

• 第一行一个正整数 \(n\)（\(1\leq n\leq 10^5\)），
• 第二行 \(n\) 个整数 \(c_1,\cdots, c_n\) 描述序列 \(c\)（\(1\leq c_i\leq n\)）。

保证所有数据中 \(n\) 的和不超过 \(5\times 10^5\)。

Output

对于每组数据输出一行一个整数表示答案。

Sample

1
7
1 2 3 4 3 2 1

##CASE##
1
9
1 1 1 1 1 2 2 2 2

3

##CASE##
7

Hint

【样例解释 #0】

一种选择的方法是选择区间 \([2,5]\)，再选择颜色 \(2,3\)，出现次数分别为 \(2,1\)，按位或的结果为 \(3\)，可以证明没有更优的解法。

Source

Author

THU