Có bao nhiêu số từ A đến B mà tổng các chữ số của nó là số nguyên tố.

Input: Hai số A, B ~(0 <A≤B≤ 10^8)~.</p>

Output: Số lượng số tìm được

Ví dụ:

INPUT

7 20

OUTPUT

6

Giải thích: Có 6 số thoả mãn là 7, 11, 12, 14, 16, 20

Cho số n ~(1≤ n ≤ 10^{10000})~. Tìm số lượng số không âm nhỏ hơn ~n~, có tổng bình phương các chữ số của nó chia hết cho ~3~.

Input: Số ~n~

Output: Số lượng số tìm được. Chỉ ghi ra số dư của kết quả chia cho ~10^9+7~.

Ví dụ:

INPUT 1

9

OUTPUT 1

3

INPUT 2

10

OUTPUT 2

4

INPUT 3

9

OUTPUT 3

3

Trong tiết học về dãy số tại trường, thầy giáo của Tý cho cả lớp chơi một trò chơi như sau:

Cho một dãy số ~A~ bao gồm ~N~ ~(N\leq 5*10^4)~ số nguyên, yêu cầu hãy chia dãy số trên thành hai phần liên tiếp sao cho tổng các số ở phần bên trái bằng tổng các số ở phần bên phải. Với mỗi bước như vậy bạn được 1 điểm còn nếu không thể chia được thì trò chơi sẽ kết thúc. Sau khi chia thành công bạn sẽ được chọn dãy số bên trái hoặc bên phải để tiếp tục cuộc chơi với các bước như trên cho đến khi trò chơi kết thúc.

Là một học sinh giỏi trong lớp, Tý muốn đạt được số điểm cao nhất có thể. Bạn hãy tính xem số điểm lớn nhất mà Tý có thể đạt được là bao nhiêu?

Dữ liệu vào:

• Dòng đầu tiên ghi một số nguyên ~T~ (1 ≤ ~T~ ≤ 10) là số lượng bộ dữ liệu. Mỗi bộ liệu bao gồm hai dòng:
• Dòng đầu tiên ghi một số nguyên ~N~ là số lượng phần tử của dãy ~A~.
• Dòng thứ hai gồm ~N~ phần tử của dãy ~A~ được ghi cách nhau bởi dấu cách (0 ≤ ~a_i~ ≤ ~10^9~).

Kết quả: Với mỗi bộ dữ liệu in ra một số nguyên trên một dòng là kết quả của bộ dữ liệu đó.

Ví dụ

Input

3
3
3  3  3
4
2  2  2  2
7
4  1  0  1  1  0  1

Output

0
2
3

Cho dãy ~A~ gồm ~N~ số nguyên dương ~a_1~, ~a_2~, ..., ~a_N~. Một dãy con của ~A~ là một dãy khác rỗng thu được bằng cách chọn ra từ ~A~ một số phần tử và giữ nguyên thứ tự của chúng.

Với một dãy con ~A_i={a_{i1},𝑎_{i2},…,a_{ik}}, S=a_{i1} + a_{i2}+…+a_{ik}~ gọi là tổng của dãy con đó.

Cho trước hai số nguyên dương ~P~ và ~Q~, có bao nhiêu giá trị ~S~ khác nhau từ các tổng của các dãy con của ~A~, lớn hơn hoặc bằng ~P~ và bé hơn hoặc bằng ~Q~ ~(P ≤ S ≤ Q)~.

Dữ liệu vào gồm:

• Dòng đầu ghi ba số nguyên dương ~N, P, Q~ ~(1 ≤ N ≤ 100, 1 ≤ P < Q ≤ 100)~
• Dòng tiếp theo ghi ~N~ số nguyên dương của dãy ~A~, mỗi số cách nhau một dấu cách ~(0 < a_i ≤ 100, i = 1, 2, …, N)~.

Kết quả gồm một dòng ghi một số là số dãy con tìm được.

Ví dụ

INPUT

6 3 7
8 2 3 10 5 5

OUTPUT

3

Giải thích

Có 3 tổng có giá trị khác nhau: 3, 5, 7 (2 + 5).

Biết rằng:

• Có 30% số tests có ~N ≤ 20~.
• Có 60% số tests có ~N ≤ 40~.

Cho lưới ô vuông gồm ~m~ dòng ~n~ cột. Các dòng được đánh số từ 1 đến ~m~, các cột được đánh số từ 1 đến ~n~. Trên các ô vuông nhỏ có ghi số 0 hoặc số 1. Yêu cầu: In ra kích thước hình vuông (độ dài cạnh) lớn nhất chứa gồm toàn số 1 trong lưới ô vuông đã cho.

Dữ liệu

• Dòng đầu tiên chứa hai số nguyên dương ~m~ và ~n~ (~m~, ~n~ ≤ 1000);
• ~M~ dòng tiếp theo, mỗi dòng chứa n số mang giá trị 0 hoặc 1 biểu diễn lưới các ô vuông.

Kết quả

• In ra kích thước hình vuông lớn nhất tìm được.

Ví dụ

Sample input

4 5
1 1 1 0 1
1 1 0 0 1
1 1 1 1 1
1 1 1 1 1

Sample output

2

Giải thích: hình vuông góc trái trên là ô (2, 1) và góc phải dưới là ô (3, 2) là hình vuông có kích thước lớn nhất tìm được.

Cho ma trận ~A~ có ~N × M~ phần tử. Phần tử ở hàng ~i~ cột ~j~ có giá trị là ~A_{i,j}~.

Bạn được chọn không quá ~\lfloor\frac{M}{2}\rfloor~ phần tử trên mỗi hàng. Bạn hãy chọn sao cho tổng các phần tử chia hết cho ~K~ và có tổng là lớn nhất.

Dữ liệu

• Dòng đầu tiên gồm số nguyên ~N,M,K (1≤ N,M,K ≤70)~.
• ~N~ dòng tiếp theo, mỗi dòng chứa ~M~ số nguyên biểu diễn cho ma trận ~A~. Dòng thứ ~i~ cột ~j~ có giá trị là ~A_{i,j}\ (1≤ A_{i,j} ≤70)~.

Kết quả

• Một số nguyên duy nhất thể hiện tổng các phần tử đã chọn.

Ví dụ

Sample Input 1

3 4 7
51  2 6 7
52  62 65 5
6 6 62 62

Sample Output 1

308

Giải thích

• Hàng 1 chọn 51 và 6
• Hàng 2 chọn 62 và 65
• Hàng 3 chọn 62 và 62
• Tổng các phần tử chọn là: ~51+6+62+65+62+62=308~ chia hết cho ~7~

Chấm điểm

• Subtask 1 (50% số test): ~1≤ N × M ≤20~
• Subtask 2 (50% số test): Không có ràng buộc gì thêm

Nguồn: Free Contest

Ví dụ:

INPUT

5 4
3 5 7 9 10
3 4 9 11

OUTPUT

2

Sau khi tìm ra được các tín hiệu, nhận lệnh từ cấp trên, chỉ huy Gabriel Lorca của tàu USS Discovery muốn đưa tàu đến đó để tìm hiểu thêm về các tín hiệu. Sự di chuyển trong mạng lưới bào tử sợi nấm được đảm nhiệm bởi 1 thứ gọi là Động cơ bào tử, động cơ bào tử cần sử dụng trung gian là 1 con Tardigrade để làm hoa tiêu dẫn đường trong mạng lưới sợi nấm.

Nhưng năng lượng tác động lên sinh vật đó sau mỗi lần nhảy quá lớn nên chỉ trong vài lần sau đó, con Tardigrade duy nhất đã rơi vào trạng thái ẩn sinh tột độ bằng cách giảm lượng nước trong cơ thể xuống dưới 1%. Đang trong thời chiến và loài Tardigrade cũng đang trong nguy cơ tuyệt chủng, họ không thể làm gì khác ngoài việc cố gắng hồi sức cho nó. Trong tình thế gấp gáp, 1 ý tưởng táo bạo nhưng không kém phần xuất sắc đó là hợp nhất DNA của Tardigrade vào cơ thể trung úy Paul Stamets (là người khám phá ra động cơ bào từ). Dù thử nghiệm thành công nhưng với số hành tinh cần kiểm tra quá lớn dẫn đến số lần nhảy có thể rất nhiều. Paul Stamets muốn biết được ngưỡng năng lượng lớn nhất qua hàng loạt các cú nhảy để có biện pháp phòng ngừa kịp thời. Năng lượng qua các lần nhảy sẽ biến động tuần hoàn theo chu kì mà trung úy Paul sẽ cung cấp cho các bạn ngay bên dưới. Các bạn hãy giúp anh ấy nhé!

-Yêu cầu

Các hành tinh được xem như 1 dãy số. Năng lượng cần để nhảy đến hành tinh ~i~ là ~a[i]~. Paul sẽ thực hiện 1 số lần nhảy bất kì ~(\geq1)~ và năng lượng qua các lần nhảy như sau: VD: số lần nhảy là ~k~ ~(i_1 < i_2 < … < i_k)~ thì năng lượng tổng: ~3 \cdot a[i_1] + 1 \cdot a[i_2] - 4 \cdot a[i_3] + 3 \cdot a[i_4] + 1 \cdot a[i_5] - 4 \cdot a[i_6] + ….. a[i_k]~

Tìm năng lượng tổng lớn nhất

INPUT

Dòng đầu tiên chứa ~T~ là số testcase ~(T \leq 10)~

+~T~ nhóm, mỗi nhóm có dạng:

+~N~ là số hành tinh ~(N \leq 10^5)~

+Tiếp theo là ~N~ số ~a[i]~ ~(-10^5 \leq a[i] \leq 10^5)~ biểu thị năng lượng khi nhảy đến hành tinh ~i~

OUTPUT

In ra ~T~ dòng, mỗi dòng là kết quả của testcase đó

Sample input 1

1
5
-7 -9 -2 8 2

Sample output 1

26

Sample input 2

1
2
-4 -3

Sample output 2

-9

*Giải thích test 1: Paul sẽ chọn ~i = 4~ và ~i = 5~, khi đó năng lượng sẽ là ~3 \cdot 8 + 1 \cdot 2 = 26~

Có thế thấy không có cách chọn nào để năng lượng lớn hơn

*Tính điểm: *

Subtask 1: ~T = 1, n \leq 20~ (25%)

Subtask 2: ~T = 10, n \leq 10^3~ (50%)

Subtask 3: Không có ràng buộc gì thêm (25%)

Cho dãy số nguyên dương gồm ~N~ số, hãy tìm dãy con tăng dài nhất.

Một dãy con tăng là một dãy số gồm các phần tử ở vị trí ~i_1 < i_2 < ... < i_m~ sao cho ~a_{i_1} < a_{i_2} < a_{i_3} < ... < a_{i_m}~.

Input

• Dòng đầu chứ số ~N (N \leq 10^5)~ là số phần tử của dãy.
• Dòng tiếp theo chứ ~N~ số nguyên dương ~a_i (a_i \leq 10^9)~.

Output

• Một số nguyên duy nhất là độ dài dài nhất của dãy con tăng.

Ví dụ

Example Input

5
2 6 3 1 5

Example Output

3

Subtask

• Subtask 1: ~20~% số tests có ~N \leq 10^3, a_i \leq 10^9~.
• Subtask 2: ~40~% số tests có ~N \leq 10^5, a_i \leq 10^5~.
• Subtask 3: ~40~% số tests có ~N \leq 10^5, a_i \leq 10^9~.