#include
#include
using namespace std;
int kadane(int a[] , int n)
{
int cs = 0 ;
int ms = 0 ;
for(int i = 0 ; i < n ; i++)
{
cs = cs + a[i];
if (cs < 0)
cs = 0;
if (ms < cs)
ms = cs;
}
return ms;
}
int maxcircularsum(int a[] , int n)
{
int max_kadane = kadane(a , n);
int max_wrap = 0,i;
for(int i =0 ; i<n;i++)
{
max_wrap += a[i];
a[i] = - a[i];
}
max_wrap = max_wrap + kadane(a,n);
return (max_wrap > max_kadane) ? max_wrap : max_kadane ;
}
main()
{
int ts;
cin>>ts;
while(ts > 0)
{
int n;
cin>>n;
int a[n];
for(int i = 0 ; i < n ; i++)
{
cin>>a[i];
}
cout << maxcircularsum(a,n);
ts–;
}return 0;
}