Tom came up with a terrible way to catch Jerry. He set a trap in front of Jerry's house.And there is some cheese in the trap. This cheese is a magic cheese, and if you eat one x cheese, Jerry's weight will increase by x. Then, once Jerry starts eating cheese, the trap kicks in. And it catches Jerry when he stops eating cheese. But there's a problem. The trap doesn't catch Jerry when he weighs a perfect square. Of course the clever Jerry wanted to eat cheese as much as possible. Suppose Jerry's weight started from zero. Now, is there any way you can help him eat as much cheese as possible?

The first line of the date is an integer T, which is the number of the text cases.

Then T cases follow, each case contains one integers N which is the number of cheese.

The second line have n integers w which is the weight of cheese

T <= 20

1<= n <= 20

1<= w <= 1,000,000

For each case, output the maximum number of cheese you can eat in a line.