题面描述

给定一个长度为 $n$ 的数组 $a$ ，我们定义：

• $f(a) = a_1 \oplus a_2 \oplus \cdots \oplus a_n$ （$\oplus$ 表示按位异或）
• $g(a) = \gcd(a_1, a_2, \ldots, a_n)$ （$\gcd$ 表示所有元素的最大公约数）

我们需要从数组 $a$ 中选取一个 非空的连续子数组 $b$ ，使得

题目内容

小苯有一个长度为$n$的数组$a$。他定义:

$f(a)=a_1 \oplus a_2 \oplus ... \oplus a_n$。(即所有数字的异或和).

$g(a)=gcd(a_1,a_2,.,a_n)$。(即所有数字的最大公约数)。

现在小苯希望你从$a$中选择一个非空子数组$b$(子数组需满足连续)，满足子数组的$f(b)·g(b)$尽可能大，请你帮他算一算这个最大值吧。

输入描述

第一行一个正整数$T(1≤T≤1000)$，表示测试数据的组数。

接下来对于每组测试数据，输入包含两行。

第一行一个正整数$n(1≤n≤2×10^5)$，表示数组a的长度。

第二行$n$个整数$a_i(0≤a_i≤10^9)$,表示数组$a$。

(保证所有测试数据中$n$的总和不超过$3×10^5$。)

输出描述

对于每组测试数据，输出一行一个整数表示最大的$f(b)·g(b)$值.

补充说明

注意:$gcd(0,x)=x$,即$0$与任意数$x$的最大公约数都是任意数$x$。

样例1

输入

1
4
1 1 1 1

输出

1 

说明

可以选择区间$[1,3]$对应子数组为${1, 1,1}$,$f$和$g$值都为$1$，乘积也为$1$，可以证明不存在更优的答案。