给定一个长度为 $n$ 的颜色序列 $c$。

定义 $\text{occ}(x, l, r)$ 为颜色 $x$ 在序列 $c$ 的第 $l$ 项到第 $r$ 项之间出现的次数。

请找出一个区间 $[l, r]$ 以及两个颜色 $x, y$（注意 $x, y$ 可以相等），使得 $\text{occ}(x, l, r) \text{ or } \text{occ}(y, l, r)$ 的值最大，其中 $\text{or}$ 为按位或运算。

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$ ($1 \le T \le 10^5$)，表示测试数据的组数。对于每组测试数据：

第一行包含一个正整数 $n$ ($1 \le n \le 10^5$)。

第二行包含 $n$ 个整数，表示序列 $c$ ($1 \le c_i \le n$)。

保证所有测试数据的 $n$ 之和不超过 $5 \times 10^5$。

输出格式

输出一行一个整数，表示答案。

样例

输入格式 1

1
7
1 2 3 4 3 2 1

输出格式 1

3

说明

对于第一个测试样例，一种可能的选择是区间 $[2, 5]$ 并选择颜色 2 和 3，它们的出现次数分别为 2 和 1，按位或的结果为 3。可以证明不存在更好的解。

输入格式 2

1
9
1 1 1 1 1 2 2 2 2

输出格式 2

7