题目描述

奔奔找到了一些长为$n$的序列，序列的第$i$个数为$a_i$。奔奔希望取出序列的一个区间带走，如果奔奔选择带走区间$[l,r]$，那么奔奔的收益为:

$a_l+a_{l+1}+a_{l+2}+...+a_r+gcd(a_l,a_{l+1},a_{l+2},...,a_r)$

$gcd(a_l,a_{l+1},a_{l+2},...,a_r)$表示区间内所有数的最大公因数，​即最大的可以被区间内所有数字整除的数​。例如$gcd(12,16,24)$=4，因为4整除12,16,24，且不存在更大的同时整除这三个数字的数。

奔奔要分别带走这$T$个序列中收益最高的区间，你需要帮助奔奔找到每一个序列最高的收益及对应的区间。

输入格式

输入的第一行一个整数$T(T≤10)$，表示有$T$个序列。

接下来每两行描述一个序列，第一行一个正整数$n$表示序列的长度。

接下来一行个数字$n$，第$i$个数字为$a_i$，描述序列的内容。

输出格式

对于每一个序列输出两行。

第一行一个整数s，表示奔奔能获得的最大的收益。第二行两个整数l,r表示可以获得最大收益的方案。如果有多种方案能达到最大收益，输出任意一种即可。

样例

2
6
1 10 5 15 5 2
4
3 3 2 3

40
2 5
12
1 4

2
6
1 8 16 8 3 1
5
15 30 12 75 10

40
2 4
150
4 4

数据范围

• 对于前30%的数据，$n≤100, a_i≤100$。
• 对于前50%的数据，$n≤1000$。
• 对于前70%的数据，$a_i≤100$。
• 另有的10%数据，保证$a_i$随机生成。
• 对于100%的数据，$1≤n≤10^5, 1≤a_i≤10^6$。