Tèo có một số lá bài, trong đó có ~A_i~ lá bài ghi giá trị ~i~. Hai lá bài mang giá trị ~x,y~ có thể tạo thành một cặp nếu và chỉ nếu ~|x-y| \le 1~.

Hỏi Tèo có thể tạo tối đa bao nhiêu cặp lá bài (không có lá bài nào được nằm trong hai cặp khác nhau).

Dữ liệu:

• Dòng đầu chứa số nguyên dương ~N (1 \le N \le 10^5 )~.
• ~N~ dòng tiếp theo, mỗi dòng chứa một số nguyên ~A_i (1 \le A_i \le 10^9)~.

Kết quả:

• Gồm một số nguyên duy nhất là kết quả bài toán.

Ví dụ:

Sample Input

4
4
0
3
2

Sample Output

4

Giải thích:

• Có ~4~ lá bài ghi số ~1~; không lá bài nào ghi số ~2; 3~ lá bài ghi số ~3; 2~ lá bài ghi số ~4~.
• Có thể ghép tối đa ~4~ cặp lá bài ~(1,1), (1,1), (3,4), (3,4)~.

Cho số nguyên ~n~ hãy cho biết có bao nhiêu số nguyên tố không lớn hơn ~n~ có thể viết được dưới dạng ~x^2+y^4~ với ~x, y~ là hai số nguyên.

Dữ liệu:

• Dòng thứ nhất chứa số nguyên ~T(1 \le T \le 10000)~ là số test;

• ~T~ dòng tiếp theo mỗi dòng chứa một số nguyên ~n(1 \le n \le 10^7)~.

  Kết quả:

• Ghi ra ~T~ dòng, mỗi dòng gồm ~1~ số nguyên là đáp án bài toán.

  Ví dụ:

Sample Input

3
1
2
10

Sample Output

0
1
2

Ràng buộc:

• Có ~50\%~ số test có ~t \le 10, n \le 1000~;
• ~50\%~ số test còn lại không giới hạn gì thêm.

An tìm được trong đống giấy tờ lộn xộn của Bình một băng giấy dài ghi một xâu ~n~ ký tự. Vừa mới học ở trường bài toán tìm ước số, An nhận thấy ngay ~m~ là một ước của ~n~ và lấy kéo cắt băng giấy thành các phần bằng nhau, mỗi phần chứa đúng ~k~ ký tự. Đi học về, thấy em mình đang nghịch các mẩu giấy cắt được, Bình điếng người, đứng chết lặng. Phải tốn biết bao nhiêu công sức Bình mới tìm được xâu thích hợp làm test cho một bài tập ở giờ semina tin học và cũng phải tốn không ít công sức mới viết được nó ra giấy để trình bày. Bình bắt An phải gián các mẩu giấy lại thành xâu ban đầu, nếu không tối nay sẽ không cho mượn máy tính để chơi.

Các mẩu giấy được đánh số từ ~1~ đến ~m~.

Hãy chỉ ra trình tự lắp ghép các mẩu giấy để được xâu ban đầu.

Dữ liệu:

• Dòng đầu tiên chứa ~2~ số nguyên ~n~ và ~m (1 \le m \le n \le 10^6)~;
• Dòng thứ hai chứa xâu ban đầu, độ dài không quá ~10^6~;
• Mỗi dòng trong ~m~ dòng tiếp theo chứa xâu độ dài ~k = n/m~.

Kết quả:

• Đưa ra trên một dòng m số nguyên xác định trình tự lắp ghép các mẩu giấy. Nếu tồn tại nhiều cách lắp ghép thì đưa ra cách có thứ tự từ điển nhỏ nhất.

Ví dụ:

Sample Input

12 3
cabacaqwerty
erty
caba
caqw

Sample Output

2 3 1

Ba bạn học sinh trong lúc nhàn rỗi nghĩ ra trò chơi sau đây. Mỗi bạn chọn trước một dãy số gồm ~n~ số nguyên. Giả sử dãy số mà bạn thứ nhất chọn là: ~a_{1}, a_{2}, \ldots, a_{n}~, dãy số bạn thứ hai chọn là ~b_{1}, b_{2}, \ldots, b_{n}~ và dãy số bạn thứ ba chọn là ~c_{1}, c_{2}, \ldots, c_{n}~. Mỗi lượt chơi, bạn thứ nhất chọn một chỉ số ~i~, bạn thứ hai chọn chỉ số ~j~, bạn thứ ba chọn chỉ số ~k~ thỏa mãn: ~i \lt j \lt k~ và điểm cho lượt chơi đó bằng tích ~a_{i} \times b_{j} \times c_{k}~.

Ví dụ: Với ~n=4~, dãy số bạn thứ nhất chọn -3, 2, 3, 0; dãy số bạn thứ hai chọn 1, 1, 1, 0; còn dãy số bạn thứ ba chọn ~9,1,0,-2~. Khi đó nếu bạn thứ nhất chọn ~i=1~, bạn thứ hai chọn ~j=2~, còn bạn thứ ba chọn ~k=4~ thì lượt chơi đó được ~(-3) \times 1 \times(-2)=6~ điểm và đây là cách chọn để đạt điểm cao nhất trong số các cách chọn thỏa mãn.

Yêu cầu: Cho ba dãy số ~a_{1}, a_{2}, \ldots, a_{n}, b_{1}, b_{2}, \ldots, b_{n}~ và ~c_{1}, c_{2}, \ldots, c_{n}~. Hãy xác định điểm cao nhất trong số các cách chọn thỏa mãn.

Dữ liệu:

• Dòng đầu tiên chứa số nguyên dương ~n~;
• Dòng thứ hai chứa dãy số nguyên ~a_{1}, a_{2}, \ldots, a_{n}\left(\left|a_{i}\right| \leq 10^{6}, i=1,2, \ldots, n\right)~;
• Dòng thứ ba chứa dãy số nguyên ~b_{1}, b_{2}, \ldots, b_{n}\left(\left|b_{i}\right| \leq 10^{6}, i=1,2, \ldots, n\right)~;
• Dòng thứ tư chứa dãy số nguyên ~c_{1}, c_{2}, \ldots, c_{n}\left(\left|c_{i}\right| \leq 10^{6}, i=1,2, \ldots, n\right)~.

Kết quả:

• Ghi ra một số nguyên là điểm cao nhất trong số các cách chọn thỏa mãn.

Ví dụ:

Sample Input

4 
-3 2 3 0 
1 1 1 0 
9 1 0 -2

Sample Output

6

Ràng buộc:

• Có ~40 \%~ số test ứng với ~40 \%~ số điểm của bài có ~n \leq 300~;
• Có ~30 \%~ số test khác ứng với ~30 \%~ số điểm của bài có ~n \leq 3000~;
• Có ~30\%~ số test khác ứng với ~30\%~ số điểm của bài có ~n \leq 300000~.