CSG-CPC
Online Judge

1241 : 二合一

         Time Limit: 1 Sec     Memory Limit: 512 Mb     Submitted: 247     Solved: 80    

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\),可以证明没有更优的解法。

Author

THU