Bài tập

Trên con đường đến ngôi làng của một nàng công chúa có \(N\) chiếc rương vàng nằm nối tiếp nhau theo thứ tự đi qua. Rương thứ \(i\) chứa \(x_i\) đồng vàng. Tuy nhiên, những chiếc rương này bị yểm bùa: nếu bạn đã lấy vàng ở rương \(i-1\) thì rương \(i\) sẽ không mở ra được nữa. Nói cách khác, không được lấy hai rương liên tiếp.

Hãy tính tổng số đồng vàng lớn nhất có thể mang đi.

Input

• Dòng đầu tiên chứa số nguyên \(t\) là số bộ test.
• Mỗi bộ test gồm hai dòng: dòng đầu chứa số nguyên \(N\) là số rương; dòng tiếp theo chứa \(N\) số nguyên \(x_1, x_2, \dots, x_N\) (nếu \(N = 0\) thì dòng này để trống).

Output

Với mỗi bộ test, in ra một dòng là số vàng lớn nhất thu được.

Constraints

• \(1 \le t \le 10\)
• \(0 \le N \le 10^4\)
• \(0 \le x_i \le 10^4\)

Sample Input

3
6
4 1 1 9 1 3
0

4
5 5 5 5

Sample Output

16
0
10

Explanation

Bộ test đầu: lấy các rương 4, 9, 3 (vị trí 1, 4, 6) được \(16\). Bộ test thứ hai không có rương nào. Bộ test thứ ba: lấy hai rương cách nhau, được \(10\).

Một vật rơi tự do (không vận tốc đầu) từ độ cao \(h\) mét. Lấy gia tốc rơi tự do \(g = 9{,}8\ \text{m/s}^2\). Tính vận tốc \(v\) của vật khi chạm đất, biết \(v = \sqrt{2gh}\).

Input

Một dòng chứa số thực \(h\) (tối đa 3 chữ số thập phân).

Output

In ra \(v\) làm tròn đúng \(5\) chữ số sau dấu phẩy.

Constraints

• \(1 \le h \le 10^9\)

Sample Input

5

Sample Output

9.89949

Explanation

\(v = \sqrt{2 \cdot 9{,}8 \cdot 5} = \sqrt{98} \approx 9{,}89949\).

Bé An dùng que tính để xếp một phép cộng dạng \(x + y = z\) với \(x, y, z\) là các số nguyên dương, trong đó mỗi số nguyên dương \(v\) được biểu diễn bằng đúng \(v\) que (dấu + và = không tốn que). Ví dụ \(1+2=3\) cần \(6\) que, \(1+1=2\) cần \(4\) que.

An đang có \(N\) que và muốn dùng hết toàn bộ số que để xếp thành một phép cộng như trên. Hỏi An cần lấy thêm ít nhất bao nhiêu que? (In \(0\) nếu không cần lấy thêm.)

Input

• Một số nguyên dương \(N\).

Output

• In ra số que ít nhất cần lấy thêm.

Constraints

• \(1 \le N \le 10^9\)

Sample Input

5

Sample Output

1

Explanation

Phép cộng dùng \(x + y + z = 2z\) que, là số chẵn và ít nhất \(4\). Với \(N = 5\) cần thêm \(1\) que để được \(6\) que, ví dụ \(1+2=3\).

Nam bị phạt trong giờ thể dục: bạn đứng nghiêm trên một đường thẳng, thầy hô \(n\) lần. Mỗi lần thầy hô một trong hai lệnh: lệnh mã \(1\) nghĩa là Nam bước sang trái \(1\) mét, lệnh mã \(2\) nghĩa là Nam bước sang phải \(1\) mét. Hỏi sau \(n\) lệnh, Nam cách chỗ xuất phát bao nhiêu mét?

Input

• Dòng đầu: số nguyên \(n\).
• Dòng sau: \(n\) số, mỗi số là \(1\) (trái) hoặc \(2\) (phải).

Output

Khoảng cách từ vị trí cuối cùng của Nam đến vị trí ban đầu.

Constraints

• \(1 \le n \le 1000\)

Sample Input

5
2 2 1 2 2

Sample Output

3

Explanation

Bước phải \(4\) lần, bước trái \(1\) lần, kết quả cách xuất phát \(3\) mét.