Một đoạn số có tổng bằng nhau trong một dãy số là một nhóm các số theo đúng thứ tự ban đầu trong dãy mà nếu nhóm với nhau thì sẽ cho ra cùng một giá trị tổng.

Ví dụ với dãy: 2 5 1 3 3 7 thì ta có thể nhóm thành: (2 5) (1 3 3) (7) cùng cho giá trị tổng là 7.

Chú ý: đoạn đặc biệt chứa tất cả các phần tử của dãy cũng được coi là một đoạn có tổng bằng nhau với chính giá trị tổng của số của dãy đó.

Yêu cầu: viết chương trình nhận vào các dãy số nguyên dương và trả về giá trị tổng nhỏ nhất có thể của một đoạn tổng bằng nhau trong dãy.

Input

• Dòng đầu chứa số nguyên ~t~ (~1 ≤ t ≤ 1000~) là số lượng bộ test.
• Tiếp theo là ~t~ bộ test, mỗi bộ test bao gồm:
  • Dòng đầu chứa thứ tự bộ test và số nguyên ~M~ (~1 ≤ M ≤ 10000~) là số phần tử của dãy.
  • Dòng tiếp theo ghi ~M~ số của dãy phân cách bởi 1 dấu cách. (Các số trong dãy đều nhỏ hơn ~20000~).

Output

• Ghi ra cho mỗi bộ test, in ra trên một dòng gồm số thứ tự bộ test và tổng nhỏ nhất có thể đạt được của các đoạn số có tổng bằng nhau.

Sample Test

Input

3
1 6
2 5 1 3 3 7
2 6
1 2 3 4 5 6
3 20
1 1 2 1 1 2 1 1 2 1 1 2 1 1 2 1 1 2 1 1

Output

1 7
2 21
3 2