Billy and Bob are best friends but when it comes to playing a game they do not let it go easily. They fight neck and neck, be it Chess, Go, etc. They are bored with playing old, classical games that involves standard opening theories. They have got their hands on some new game which is described as follows.

There are \(N +\ 1\) buckets in a row. First \(N\) buckets contain \(1\) or more balls and the last bucket is empty. In a turn, a player can draw \(1\) or more balls from a bucket such that a maximum of \(floor(\sqrt{X})\) balls are left in that bucket where \(X\) is the number of balls present in that bucket at that point of time. A player will lose if there is nothing left to draw.

Bob is going to start the game but we want Billy to win. So, what is the minimum number of balls that need to be added to the \((N\ +\ 1)^{th}\) bucket, so that our favorite Billy wins. Needless to say, both players will be playing optimally.

Input format

First line: An integer \(T\) denoting the number of test cases
In each test case:
- First line: Integer \(N\) as described in the problem statement
- Second line: \(N\) integers denoting the number of balls in each bucket

Output format

Print the minimum number of balls that have to be put in the \((N\ +\ 1)^{th}\) bucket.

Constraints

\(1 \le T \le 10\)

\(1 \le N \le 10^{5}\)

The number of balls in the input buckets do not exceed \(10^{9}\)