Today Alex was brought array a1,a2,…,an of length n. He can apply as many operations as he wants (including zero operations) to change the array elements.

In 1 operation Alex can choose any l and r such that 1≤l≤r≤n, and multiply all elements of the array from l to r inclusive by ?1

. In other words, Alex can replace the subarray [al,al+1,…,ar] by [?al,?al+1,…,?ar] in 1 operation.

For example, let n=5, the array is [1,?2,0,3,?1], l=2 and r=4, then after the operation the array will be [1,2,0,?3,?1].

Alex is late for school, so you should help him find the maximum possible sum of numbers in the array, which can be obtained by making any number of operations, as well as the minimum number of operations that must be done for this.

Input

The first line contains a single integer t (1≤t≤104) — number of test cases. Then the descriptions of the test cases follow.

The first line of each test case contains one integer n (1≤n≤2?105) — length of the array.

The second line contains n integers a1,a2,…,an (?109≤ai≤109) — elements of the array.

It is guaranteed that the sum of n for all test cases does not exceed 2?105.

中文：

今天 Alex 被帶來(lái)了長(zhǎng)度為 n 的數(shù)組 a1,a2,…,an。 他可以應(yīng)用任意數(shù)量的操作（包括零操作）來(lái)更改數(shù)組元素。

在 1 次操作中，Alex 可以選擇任意 l 和 r，使得 1≤l≤r≤n，并將數(shù)組中從 l 到 r 的所有元素乘以 -1

。 換句話說(shuō)，Alex 可以在 1 次操作中用 [?al,?al+1,…,?ar] 替換子數(shù)組 [al,al+1,…,ar]。

例如，令n=5，數(shù)組為[1,?2,0,3,?1]，l=2，r=4，則運(yùn)算后數(shù)組為[1,2,0,?3] ，?1]。

亞歷克斯上學(xué)遲到了，所以你應(yīng)該幫助他找到數(shù)組中可能的最大數(shù)字之和（可以通過(guò)任意次數(shù)的運(yùn)算獲得），以及為此必須完成的最小運(yùn)算次數(shù)。

輸入

第一行包含一個(gè)整數(shù) t (1≤t≤104) — 測(cè)試用例的數(shù)量。 然后是測(cè)試用例的描述。

每個(gè)測(cè)試用例的第一行包含一個(gè)整數(shù) n (1≤n≤2?105) — 數(shù)組的長(zhǎng)度。

第二行包含 n 個(gè)整數(shù) a1,a2,…,an (?109≤ai≤109) — 數(shù)組的元素。

保證所有測(cè)試用例的 n 之和不超過(guò) 2?105。

-----------------------------------------------------------------

第一個(gè)輸出的是數(shù)組的絕對(duì)值之和，第二個(gè)輸出的是負(fù)數(shù)的區(qū)間個(gè)數(shù)，這里面用2個(gè)參數(shù)去處理，一個(gè)是布爾值，一個(gè)是累加數(shù)字；下面是代碼：