Bảo hỏi Đức : Số 11 và số 12 có điểm chung gì liên quan đến số nguyên tố? Sau khi suy nghĩ, Đức nhận ra các số trên có chung đặc điểm là tổng bình phương các chữ số của chúng là một số nguyên tố. Ví dụ số 11 ta có 1^2 + 1^2 = 2 là một số nguyên tố, hoặc 12 ta có 1^2 + 2^2 là một số nguyên tố.

Hai bạn đặt tên cho các số nguyên dương có tính chất này gọi là số thú vị.

Cho số nguyên dương N, hãy tìm số thú vị nhỏ nhất lớn hơn N.

Đầu vào

Dòng đầu tiên chứa số nguyên dương T là số bộ dữ liệu vào của bài toán (T ≤ 10^5)

T dòng tiếp theo, mỗi dòng chứa một số nguyên dương n (n ≤ 10^6).

Giới hạn

• Có 40% số test ứng với 40% số điểm thỏa mãn T= 1 và n ≤ 10^3

• Có 40% số test ứng với 40% số điểm thỏa mãn T≤ 10^3 và n ≤ 10^3

• 20% số test còn lại ứng với 20% số điểm không có ràng buộc gì thêm.

Đầu ra

In ra kết quả của mỗi test trên từng dòng

Ví dụ :

Input 01

3
9
11
2358

Output 01

11
12
2362

Một cảng biển có nhiều cầu cảng để tiếp nhận các tàu cập bến. Tại một thời điểm, cảng biển có thể tiếp nhận nhiều tàu. Có n tàu xin đăng ký vào cảng biển, tàu thứ i muốn đậu ở cảng từ thời điểm s đến hết thời điểm t (s ≤ t).

Có thể xem thời gian tàu thứ i muốn đậu ở cảng là một khoảng [s, t] trên trục thời gian. Tàu đã vào cầu cảng thì sẽ đậu ở đó trong suốt thời gian nằm cảng, tức là cảng biển sẽ phục vụ tàu tất cả các thời điểm trong khoảng thời gian tàu neo đậu.

Ban quản lý cảng biển muốn biết các thời điểm mà cảng biển không phục vụ tàu nào để tiến hành sửa chữa, nâng cấp các cầu cảng

Yêu cầu : Cho bảng đăng ký là khoảng thời gian xin vào cảng của n tàu, hãy tính số thời điểm cảng không phục vụ tàu nào tính từ thời điểm phục vụ tàu đầu tiên cho tới khi tàu cuối cùng rời cảng.

Đầu vào

Dòng đầu tiên chứa một số nguyên dương n ≤ 10^6

n dòng tiếp theo, mỗi dòng chứa 2 số nguyên dương s, t (1 ≤ s≤ t ≤ 10^9)

Giới hạn

Có 40% số test ứng với 40% số điểm thỏa mãn n ≤ 10^3, 1≤s ≤ t ≤ 10^3;

Có 40% số test ứng với 40% số điểm thỏa mãn n ≤ 10^5, 1≤s ≤ t ≤ 10^9;

Có 20% số test còn lại ứng với 20% số điểm thỏa mãn n ≤ 10^6, 1≤s ≤ t ≤ 10^6

Đầu ra

Ghi ra một số nguyên dương duy nhất là số thời điểm cảng không phục vụ tàu nào.

Ví dụ :

Input 01

4
1 3
7 8
2 4
10 12

Output 01

3

Giải thích test :

Thời điểm phục vụ tàu đầu tiên: 1

Thời điểm phục vụ tàu cuối cùng: 12

Trong khoảng [1,12] có các thời điểm 5, 6, 9 cảng không phục vụ tàu nào

Một cầu cảng có n gói hàng được đánh số từ 1 đến n. Gói hàng thứ i có trọng lượng a[i], các gói hàng được đặt trên băng chuyền theo tuần tự từ 1 đến n và lần lượt đưa lên các kiện hàng.

Băng chuyền có một hệ số hoạt động k, trong quá trình vận hành nếu các gói hàng liên tiếp có trọng lượng không vượt quá k thì băng chuyền cho vào cùng một kiện hàng, sau đó băng chuyền chuyển sang kiện hàng tiếp theo. Ban quản lý cảng biển muốn khảo sát các hệ số hoạt động k để tính số gói hàng nhiều nhất của một kiện hàng.

Yêu cầu : Cho trọng lượng của n gói hàng và Q số nguyên dương k là hệ số hoạt động của băng chuyền cần khảo sát. Với mỗi số nguyên dương k hãy tính số gói hàng nhiều nhất của một kiện hàng

Đầu vào

Dòng đầu tiên chứa hai số nguyên dương n và Q (1 ≤ n, Q ≤ 10^5)

Dòng thứ hai chứa n số nguyên dương a1, a2, ..., an (1 ≤ ai ≤ 10^9) là trọng lượng của các gói hàng

Q dòng tiếp theo, mỗi dòng chứa một số nguyên dương k (1 ≤ k ≤ 10^9).

Giới hạn

• Có 20% số test ứng với 20% số điểm thỏa mãn: Q = 1, n ≤ 10^2

• 40% số test khác ứng với 40% số điểm thỏa mãn: Q, n ≤ 10^3

• 40% số test còn lại ứng với 40% số điểm không có ràng buộc gì thêm.

Đầu ra

Ghi ra Q dòng, mỗi dòng ghi một số nguyên dương tương ứng là kết quả tính được theo dữ liệu vào.

Ví dụ :

Input 01

6 3
4 2 3 5 8 1
4
12
2

Output 01

3
6
1

Giải thích test :

Với k = 4: Kiện hàng nhiều gói hàng nhất tìm được có 3 gói hàng liên tiếp trọng lượng không lớn hơn 4 là: 4, 2, 3;

Với k = 12: Tất cả 6 gói hàng có trọng lượng nhỏ hơn 12 nên vào cùng 1 kiện hàng;

Với k = 2: Có 2 kiện hàng có cùng số gói hàng là 1.