题目描述

鸭哥有一个长度为$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)\times g(b)$尽可能大，请你帮他算一算这个最大值吧。

输入描述

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

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

第一行输入一个正整数$n(1\le n\le 2\times 10^5)$，表示数组$a$的长度。

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

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

输出描述

对于每组测试数据，输出一行一个整数表示最大的$f(b)\times 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$，可以证明不存在更优的答案。