Cho một số tự nhiên ~N~. Hãy cho biết số ~N~ có là tổng của hai số tự nhiên liên tiếp hay không.

Input

Gồm một số tự nhiên ~N~ duy nhất. (~1 \leq N \le 10^9~)

Output

In ra YES nếu ~N~ là tổng của hai số tự nhiên liên tiếp, ngược lại in ra NO.

Sample Test 1

Input:

5

Output:

YES

Note: Do ~5 = 2 + 3~ nên ~5~ là tổng của hai số tự nhiên liên tiếp.

Sample Test 2

Input:

6

Output:

NO

Cho một số tự nhiên ~N~. Hãy cho biết số ~N~ có là tổng của ~4~ số tự nhiên liên tiếp hay không, nếu có hãy đưa ra số nhỏ nhất trong ~4~ số đó.

Input

Gồm một số tự nhiên ~N~ duy nhất. (~N \le 10^9~)

Output

In ra số nhỏ nhất trong ~4~ số nếu ~N~ là tổng của ~4~ số tự nhiên liên tiếp, ngược lại in ra NO.

Sample Test 1

Input:

10

Output:

1

Note: Do ~10 = 1 + 2 + 3 + 4~ nên ~10~ là tổng của bốn số tự nhiên liên tiếp.

Sample Test 2

Input:

12

Output:

NO

Cho hai số tự nhiên ~N~ và ~k~. Hãy cho biết số ~N~ có là tổng của ~k~ số tự nhiên liên tiếp hay không, nếu có hãy đưa ra số nhỏ nhất trong ~k~ số đó.

Input

Gồm hai dòng, dòng thứ nhất chứa số tự nhiên ~N~ và dòng thứ hai chứa số tự nhiên ~k~. (~N, k \le 10^9~, ~k \ge 1~)

Output

In ra số nhỏ nhất trong ~k~ số nếu ~N~ là tổng của ~k~ số tự nhiên liên tiếp, ngược lại in ra NO.

Sample Test 1

Input:

10
4

Output:

1

Note: Do ~k = 4~, ~10 = 1 + 2 + 3 + 4~ nên ~10~ là tổng của ~k~ số tự nhiên liên tiếp.

Sample Test 2

Input:

15
3

Output:

4

Note: ~15 = 4 + 5 + 6~

Sample Test 3

Input:

50
6

Output:

NO

Một số nguyên dương ~A~ được gọi là hoàn hảo nếu ~2 \times A \leq K~ (trong đó ~K~ là tổng các ước dương của ~A~).

Ví dụ: số ~12~ được coi là số hoàn hảo vì ~2 \times 12 \leq K~ với ~K = 1 + 2 + 3 + 4 + 6 + 12 = 28~

Cho ~N~ số nguyên dương ~A_1, A_2, \ldots, A_n~, hãy đếm số lượng số hoàn hảo trong dãy đã cho.

Input

• Dòng đầu tiên chứa số nguyên dương ~N~. (~N \leq 10^4~)
• ~N~ dòng tiếp theo, dòng thứ ~i~ chứa số nguyên dương ~A_i~. (~A_i \leq 10^6~)

Output

In ra số lượng số hoàn hảo trong dãy đã cho.

Sample Test

Input:

5
8
16
12
6
7

Output:

2

Cho một dãy gồm ~N~ số nguyên dương ~a_1, a_2, a_3, ..., a_N~. Biết rằng các số trong dãy đều xuất hiện hai lần, trừ một số. Hãy tìm số đó.

Input

• Dòng thứ nhất chứa số nguyên dương ~N~.
• Dòng thứ hai chứa ~N~ số nguyên dương ~a_1, a_2, a_3, ... a_N~. (~a_i \leq 10^6~)
• Các số đều xuất hiện hai lần trừ một số.

Output

• In ra số chỉ xuất hiện một lần trong dãy.

Subtasks

• Subtask 1 (~20\%~ số điểm): ~N = 3~.
• Subtask 2 (~30\%~ số điểm): ~N \leq 10^3~.
• Subtask 3 (~50\%~ số điểm): ~N \leq 10^6~.

Sample Test 1

Input

5
4 1 2 1 2

Output

4

Cho dãy ~A~ gồm ~n~ phần tử, phần tử thứ ~i \ (1 \le i \le n)~ có giá trị ~a_i~.

Bạn có thể biến đổi dãy ~A~ bằng thao tác sau: Chọn hai phần tử liên tiếp trong dãy và thay thế hai phần tử này bằng tổng của chúng.

Hãy đếm số lượng thao tác tối thiểu để dãy ~A~ là dãy đối xứng. Dãy ~A~ được coi là dãy đối xứng nếu đọc từ phải sang trái vẫn thu được dãy ~A~ ban đầu.

Input

• Dòng đầu tiên chứa số nguyên dương ~n;~
• Dòng tiếp theo chứa ~n~ số nguyên dương ~a_i \ (1 \le a_i \le 10^9)~.

Output

In ra kết quả là số thao tác tối thiểu để dãy ~A~ là dãy đối xứng.

Scoring

• Subtask 1 [30%]: ~n \le 10;~
• Subtask 2 [30%]: ~n \le 1000;~
• Subtask 3 [40%]: ~n \le 10^6.~

Examples

Input

3
1 2 3

Output

1

Giải thích: ~\textbf{1 2} \ 3 \rightarrow 3 \ 3.~

Input

5
1 2 4 6 1

Output

1

Giải thích: ~1 \ {\textbf{2 4}} \ 6 \ 1 \rightarrow 1 \ 6 \ 6 \ 1~.

Input

4
1 4 3 2

Output

2

Giải thích: ~\textbf{1 4} \ 3 \ 2 \rightarrow 5 \ \textbf{3 2} \ \rightarrow 5 \ 5~.

Một số ~X~ ban đầu được tách thành ~N~ số ~A_1, A_2, \ldots, A_n~. Hãy tìm cách ghép lại ~N~ số này, theo thứ tự bất kỳ, thành số lớn nhất có thể.

Input

• Dòng đầu tiên chứa số nguyên dương ~N~ (~N \leq 100~).
• ~N~ dòng tiếp theo, dòng thứ ~i~ chứa số ~A_i~ (độ dài số ~A_i~ không vượt quá ~100~). Lưu ý, ~A_i~ có thể có các chữ số ~0~ đứng ở đầu.

Output

• In ra số lớn nhất có thể tạo được từ việc ghép ~N~ số đã cho. Số này có thể có các chữ số ~0~ đứng ở đầu.

Sample Test

Input:

4
2
20
004
66

Output:

66220004

Cho số nguyên dương ~N~. Hãy đếm số cách xoá đi một đoạn chữ số liên tiếp của ~N~ (không được xoá hết) để nhận được số mới chia hết cho ~3~, biết rằng số mới nhận được có thể có thừa chữ số ~0~ ở đầu.

Hai cách xoá được coi là khác nhau nếu có một vị trí được xoá trong cách này nhưng không được xoá trong cách kia.

Input

• Gồm một dòng duy nhất chứa một số nguyên ~N~ (~1 \le N \le 10^{100000}~).

Output

• In ra một số nguyên là số cách xoá tìm được.

Subtasks

• Subtask 1 (~50\%~ số điểm): ~N \le 10^{300}~.
• Subtask 2 (~25\%~ số điểm): ~N \le 10^{10000}~.
• Subtask 3 (~25\%~ số điểm): Không có ràng buộc gì thêm.

Sample Test 1

Input

1005

Output

4

Sample Test 2

Input

2009

Output

3

Sau khi bán hết sách, TDZ chuyển sang mở một quán cà phê.

Qua thăm dò, TDZ đã biết trước ngày khai trương sẽ có ~n~ khách, khách thứ ~i~ sẽ vào thời điểm ~h_i~. Để phục vụ lượng khách đến dồn dập, quán cà phê có thuê thêm một số nhân viên ưu tú. Mỗi nhân viên có thể hoạt động không ngừng nghỉ, mỗi lần chỉ phục vụ một khách trong đúng ~1~ đơn vị thời gian. Nhưng nếu một vị khách tới mà không nhận được sự phục vụ ngay thì sẽ lập tức bỏ đi.

Ví dụ, một vị khách đến ở thời điểm ~5~, thì nhân viên sẽ phục vụ xong cho vị khách đó ở thời điểm ~6~ và tiếp tục phục vụ luôn khách tiếp theo (nếu có).

Hãy giúp TDZ tìm ra số lượng nhân viên cần thuê ít nhất mà vẫn đảm bảo tất cả các khách đều được phục vụ.

Input

• Dòng đầu tiên chứa số nguyên dương ~n~ (~n \leq 10^5~).
• Dòng tiếp theo chứa ~n~ số nguyên dương ~h_1, h_2, h_3, \ldots, h_n~ tương ứng với thời điểm khách đến (~h_i \leq 10^5~).

Output

In ra số lượng nhân viên ít nhất cần thuê.

Sample Test

Input:

4
1 10 45 10

Output:

2

Số nguyên tố là số gồm đúng ~2~ ước là ~1~ và chính nó. Số nửa nguyên tố là số có số lượng ước nguyên dương của nó là một số nguyên tố.

Yêu cầu: Cho 2 số nguyên dương ~a,b~, đếm số lượng số nửa nguyên tố trong đoạn ~[a,b]~.

Input

• Dòng đầu tiên gồm số nguyên dương ~T~ tương ứng với số bộ dữ liệu;
• ~T~ dòng sau, mỗi dòng gồm hai số nguyên dương ~a,b~.

Output

• Gồm ~T~ dòng, mỗi dòng ghi kết quả của bộ dữ liệu tương ứng.

Sample Input

2
6 9
100 100

Sample Output

2
0

Scoring

• Subtask ~1 \ (20\%)~: ~1\le T, a, b \le 100~.
• Subtask ~2 \ (30\%)~: ~1\le T, a, b \le 1000~.
• Subtask ~3 \ (30\%)~: ~1\le T, a, b \le 10^5~.
• Subtask ~4 \ (20\%)~: ~1\le T, a, b \le 10^6~.

Cho một dãy số gồm ~N~ số nguyên dương ~a_1, a_2, ..., a_N~ có giá trị không vượt quá ~10^6~. Tìm dãy con liên tiếp ngắn nhất có chứa ít nhất hai số nguyên tố.

Dữ liệu vào từ file văn bản DAYCON.INP:

• Dòng đầu tiên gồm một số nguyên dương ~N \ (N \le 10^6)~ là số lượng phần tử của dãy số;
• Dòng thứ hai gồm ~N~ số nguyên dương ~a_1, a_2, ..., a_N~ lần lượt mô tả các phần tử của dãy số.

Kết quả ghi ra file văn bản DAYCON.OUT:

Một số nguyên duy nhất là số lượng phần tử của dãy con thoả mãn đề bài. Trường hợp không tồn tại dãy con thoả mãn, in ra ~-1~.

Ví dụ

Input

10
3 4 8 4 5 6 1 7 4 6

Output

4

Giải thích

Chọn dãy con từ vị trí thứ ~5~ đến vị trí thứ ~8~: ~5, 6, 1, 7~.

Ràng buộc

• Có ~50\%~ số test ứng với ~50\%~ số điểm của bài thoả mãn: ~N \le 10^3; \ a_i \le 10^3~;
• ~30\%~ số test khác ứng với ~30\%~ số điểm của bài thoả mãn: ~N \le 10^6; \ a_i \le 10^3~;
• ~20\%~ số test còn lại ứng với ~20\%~ số điểm của bài không có ràng buộc gì thêm.

Cho một robot được lập trình di chuyển trên một hàng ngang gồm các ô vuông. Mỗi ô được đặt tên bằng các kí tự theo thứ tự từ ~'𝐴'~ đến ~'𝑍'~ và được lặp lại vô hạn. Ban đầu robot xuất phát ở ô thứ ~1~ có tên là ~'𝐴'~ và nhảy đến các ô tiếp theo quy luật: lần ~1~ nhảy ~1~ ô, lần ~2~ nhảy ~2~ ô, lần ~3~ nhảy ~3~ ô, ~…~, lần ~𝑁~ nhảy ~𝑁~ ô. Vậy sau ~𝑁~ lần nhảy thì robot đang ở ô nào?

Dữ liệu nhập vào từ file văn bản DKT.INP:

Gồm một số nguyên dương ~N~ là số lần nhảy của robot ~(N \le 10^9)~.

Kết quả ghi ra file văn bản DKT.OUT:

Một kí tự duy nhất là tên của ô sau ~N~ lần robot nhảy.

Ràng buộc

• Có ~60\%~ số test ứng với ~60\%~ số điểm của bài thoả mãn: ~𝑁 ≤ 10^3;~
• ~20\%~ số test khác ứng với ~20\%~ số điểm của bài thoả mãn: ~𝑁 ≤ 10^6;~
• ~20\%~ số test còn lại ứng với 20% số điểm của bài không có ràng buộc gì thêm.

Ví dụ

Input

1

Output

B

Giải thích: Sau ~1~ lần nhảy, robot ở ô thứ ~2~, có tên là kí tự ~B~.

Input

4

Output

K

Giải thích: Sau ~4~ lần nhảy, robot ở ô thứ ~11~, có tên là kí tự ~K~.

Input

7

Output

C

Giải thích: Sau ~7~ lần nhảy, robot ở ô thứ ~29~, có tên là kí tự ~C~.

Chuẩn bị Gala mừng năm mới Tết Tân Sửu 2021 của công ty HiTech, ban giám đốc quyết định có giải thưởng đặc biệt cho thành viên của công ty. Sau khi đưa ra các tiêu chí đánh giá, việc bầu chọn sẽ được thực hiện bằng cách tất cả các thành viên sẽ được bỏ phiếu cho nhau.

Hình thức bỏ phiếu được thực hiện thông qua phiếu bầu chọn online. Danh sách các thành viên của công ty được niêm yết và quy định là số thứ tự từ ~1~ đến ~N~ ~(1≤N≤5000),~ tương ứng với ~N~ ô trên phiếu bầu chọn. Sau khi thực hiện, ban tổ chức thu được các danh sách phiếu tương ứng của các thành viên công ty. Trong mỗi phiếu bầu chọn, giá trị ô ở vị trí tương ứng ghi ~'X'~ là bầu chọn cho người đó, ô ghi ~'0'~ là không bầu chọn (coi các trường hợp bầu chọn không hợp lệ là không bầu chọn).

Yêu cầu: Em hãy giúp ban tổ chức đưa ra danh sách các nhân viên có phiếu bầu chọn cao nhất.

Dữ liệu nhập vào từ file văn bản VOTE.INP:

• Dòng đầu tiên gồm số một số nguyên dương ~N~ ~(1≤N≤5000)~ là số lượng phiếu bầu chọn.
• ~N~ dòng tiếp theo mỗi dòng tương ứng là ~N~ giá trị của các phiếu đã bầu chọn.

Các kí tự cách nhau một dấu cách.

Kết quả ghi ra file văn bản VOTE.OUT:

• Dòng đầu tiên ghi số lượng người được nhiều phiếu nhất và số lượng phiếu.
• Dòng thứ hai ghi thứ tự tương ứng của những người được cao phiếu nhất đó theo thứ tự tăng dần.

Ví dụ

Input

5
X 0 X 0 X
X 0 0 X X
0 0 X 0 0
0 X 0 X 0
0 0 X X 0

Output

2 3
3 4

Giải thích:

• Người số ~1~ được ~2~ phiếu bầu chọn.
• Người số ~2~ được ~1~ phiếu bầu chọn.
• Người số ~3~ được ~3~ phiếu bầu chọn.
• Người số ~4~ được ~3~ phiếu bầu chọn.
• Người số ~5~ được ~2~ phiếu bầu chọn.
• Người số ~3~ và số ~4~ cùng được số phiếu bầu chọn lớn nhất.

Giới hạn

• Có ~70\%~ số test tương ứng với số điểm có ~N \le 1000;~
• ~30\%~ số test còn lại tương ứng với số điểm có ~N \le 5000.~

Chúng ta đã quá rõ việc một số nguyên tố (prime) là số nguyên dương lớn hơn ~1~ có duy nhất hai ước là ~1~ và chính nó. Để làm mới bài toán, hôm nay, ta sẽ định nghĩa một số TPrime là một số nguyên dương lớn hơn ~1~ gồm đúng ~3~ ước.

Cho ~n~ truy vấn, mỗi truy vấn là một số ~a~, hãy kiểm tra xem số này có phải là số TPrime hay không.

Input

• Dòng ~1~ ghi số nguyên dương ~n~ ~(1 \le n \le 3*10^5)~
• ~n~ dòng sau, mỗi dòng gồm một số nguyên dương ~a~ ~(1 \le a \le 10^{12})~ miêu tả truy vấn.

Output

• In ra ~n~ dòng, với mỗi truy vấn, nếu ~a~ là số TPrime thì in ra "YES", ngược lại in ra "NO".

Subtask

• Có ~20\%~ số test ứng với ~1 \le n \le 100, 1 \le a \le 10^4~
• Có ~30\%~ số test ứng với ~1 \le n,a \le 10^5~
• Có ~50\%~ số test còn lại không có giới hạn gì thêm.

Sample Input 1

3
4
6
7

Sample Output 1

YES
NO
NO

Nông dân John (FJ) có ~N~ con bò đang đứng trên một hàng, mỗi con đứng ở một vị trí khác nhau trên trục số. Chúng đang luyện tập ném trái bóng chày vòng vòng để chuẩn bị cho một trận thi đấu quan trọng với những con bò láng giềng. Khi FJ theo dõi, ông ta nhận ra một nhóm có ba con bò ~(X,Y,Z)~ hoàn thành hai cú ném. Con bò ~X~ ném trái bóng cho con bò ~Y~ ở bên phải cô ta, và con bò ~Y~ ném trái bóng cho con bò ~Z~ ở bên phải cô ta. FJ để ý rằng lần ném thứ hai có độ dài không quá hai lần so với lần ném đầu tiên. Hãy giúp FJ đếm xem có bao nhiêu bộ ba các con bò ~(X,Y,Z)~ mà FJ có thể theo dõi.

Input

• Dòng ~1~: Số lượng các con bò là ~N~ ~(3 <= N <=1000)~.
• Dòng ~2..1+N~: Mỗi dòng chứ một số tự nhiên là vị trí của một con bò (các số tự nhiên nằm trong khoảng ~0..10^8~).

Output

In ra Số lượng bộ ba con bò ~(X,Y,Z)~, trong đó con bò ~Y~ nằm bên phải con bò ~X~, con bò ~Z~ nằm bên phải con bò ~Y~, và khoảng cách giữa ~Y~ và ~Z~ nằm giữa ~XY~ và ~2XY~ (bao gồm cả giá trị này), trong đó ~XY~ là khoảng cách của ~X~ đến ~Y~.

Sample Test

Input:

5 
3 
1 
10 
7 
4 

Output

4

hoangduong có ~n~ cuốn sách (~1 \le n \le 2000~), và hoangduong muốn xây một kệ sách gồm nhiều tầng để chứa tất cả các cuốn sách này.

Mỗi cuốn sách có chiều rộng ~w_i~ và chiều cao ~h_i~. Các cuốn sách cần được bỏ vào các tầng kệ sách theo thứ tự. Ví dụ như tầng thứ nhất cần bỏ các cuốn sách từ ~1~ đến ~k~, tầng thứ ~2~ sẽ bắt đầu từ cuốn sách thứ ~k + 1~, và cứ thế tiếp tục. Mỗi tầng kệ sách có chiều rộng tối đa là ~L~ (~1 \le L \le 10^9~). Chiều cao của mỗi tầng kệ sách bằng với chiều cao của cuốn sách có chiều cao lớn nhất, và chiều cao của cả kệ sách bằng với tổng chiều cao của mỗi tầng kệ sách khi xếp dọc lên (bỏ qua tấm gỗ ngăn cách giữa các tầng kệ sách).

Hãy giúp hoangduong tính chiều cao thấp nhất có thể của cả kệ sách khi xếp chồng lên nhau.

INPUT

Dòng 1: Gồm hai số tự nhiên cách nhau là ~n~ và ~L~.

~n~ dòng tiếp theo mỗi dòng chứa hai số tự nhiên cách nhau là ~h_i~ và ~w_i~. (~1 \le h_i \le 10^9~, ~1 \le w_i \le L~).

OUTPUT

Một dòng duy nhất chứa chiều cao nhỏ nhất của cả kệ sách.

SAMPLE INPUT

5 10
5 7
9 2
8 5
13 2
3 8

SAMPLE OUTPUT

21

Giải thích: Có ba tầng, tầng đầu tiên chứa cuốn sách thứ nhất (chiều cao là ~5~ và chiều rộng là ~7~), tầng thứ hai chứa cuốn thứ ~2~ đến cuốn thứ ~4~ (chiều cao là ~13~, chiều rộng là ~9~), và tầng chứa cuốn sách thứ ~5~ (chiều cao là ~3~, chiều rộng là ~8~).