Bài tập

Trên bàn cờ \(10 \times 10\), một quân Mã đứng ở ô \((x, y)\) (hàng \(x\), cột \(y\)). Mỗi bước, Mã nhảy theo hình chữ \(L\): đi 2 ô theo một hướng ngang hoặc dọc rồi 1 ô theo hướng vuông góc, tức tới ô \((x + a,\; y + b)\) với \((a, b)\) là một trong 8 cặp \((\pm 1, \pm 2)\), \((\pm 2, \pm 1)\), miễn là ô mới vẫn nằm trong bàn cờ. Trên bàn cờ không có quân nào khác cản đường.

Với mỗi truy vấn, hãy đếm có bao nhiêu ô mà Mã có thể đang đứng sau đúng \(n\) bước nhảy (Mã bắt buộc phải nhảy đủ \(n\) lần, có thể quay lại ô cũ).

Input

• Dòng đầu: số nguyên \(t\) - số truy vấn.
• \(t\) dòng sau, mỗi dòng ba số nguyên \(x, y, n\).

Output

Với mỗi truy vấn in một dòng chứa số ô đếm được.

Constraints

• \(1 \le t \le 100\)
• \(1 \le x, y, n \le 10\)

Sample Input 1

3
2 9 5
6 6 1
1 1 2

Sample Output 1

50
8
10

Sample Input 2

2
8 3 4
5 5 3

Sample Output 2

49
50

Explanation

Ở truy vấn thứ hai của ví dụ 1, Mã ở giữa bàn cờ nên có đủ 8 ô đến được sau đúng một bước.

Cho một dãy gồm \(n\) số nguyên dương \(a_1, a_2, \dots, a_n\) và hai số nguyên \(L\), \(R\). Một số nguyên dương \(U\) được gọi là bội chung của dãy nếu \(U\) chia hết cho mọi phần tử \(a_i\).

Hãy đếm xem trong đoạn \([L, R]\) có bao nhiêu bội chung của dãy.

Input

• Dòng đầu tiên chứa ba số nguyên dương \(n\), \(L\), \(R\).
• Dòng thứ hai chứa \(n\) số nguyên dương \(a_1, a_2, \dots, a_n\).

Output

In ra một số nguyên duy nhất là số lượng bội chung của dãy nằm trong đoạn \([L, R]\).

Constraints

• \(1 \le n \le 20\)
• \(1 \le L \le R \le 10^9\)
• \(1 \le a_i \le 10^9\)

Sample Input

3 10 100
2 3 4

Sample Output

8

Explanation

Một số chia hết cho \(2\), \(3\), \(4\) khi và chỉ khi nó chia hết cho \(12\). Các số thoả mãn trong đoạn \([10, 100]\) là \(12, 24, 36, 48, 60, 72, 84, 96\), tức là \(8\) số.

Một cửa hàng đồ uống có chương trình đổi vỏ: cứ mang đến \(10\) vỏ chai rỗng thì được tặng thêm \(3\) chai đầy. Sau khi uống hết chai mới nhận, vỏ của nó lại có thể đem đổi tiếp.

Ban đầu Bo mua \(n\) chai (đều đầy). Hỏi Bo uống được tối đa bao nhiêu chai, tính cả chai đã mua lẫn chai được tặng?

Input

Một dòng chứa số nguyên \(n\).

Output

In ra tổng số chai Bo có thể uống.

Constraints

• \(1 \le n \le 3000\).

Sample Input 1

20

Sample Output 1

26

Sample Input 2

7

Sample Output 2

7

Explanation

Ví dụ 1: đổi \(20\) vỏ lấy \(6\) chai; uống xong có \(6\) vỏ mới, không đủ \(10\) để đổi tiếp, tổng \(20 + 6 = 26\). Ví dụ 2: chỉ có \(7\) vỏ, không đổi được.

Cho một danh sách các số nguyên trên một dòng. Hãy sắp xếp chúng theo thứ tự không tăng (từ lớn đến bé) và in ra.

Input

Một dòng duy nhất chứa danh sách các số nguyên, cách nhau bởi dấu cách (ít nhất một số).

Output

In ra các số đã sắp xếp trên một dòng, cách nhau một dấu cách.

Constraints

• Danh sách có tối đa \(200\,000\) số.
• \(|a_i| \le 10^9\)

Sample Input

9 -2 5 5 0 -7 3

Sample Output

9 5 5 3 0 -2 -7