Yêu cầu

Một số nguyên dương được gọi là số chính phương nếu căn bậc hai của nó là một số nguyên dương. Hay nói cách khác, bình phương của một số nguyên dương được gọi là một số chính phương.

Ví dụ: 9 là số chính phương vì sqrt(9) = 3 hay 3^2=9, nên 9 là số chính phương. nhưng 10 thì không phải số chính phương vì sqrt(10) ≈ 3,16228.

Hãy cho biết từ X tới Y (kể cả X và Y) có tất cả bao nhiêu số chính phương?

Dữ liệu vào: Cho tệp văn bản CPP.INP chứa hai số nguyên dương X và Y được ghi trên một dòng và phân cách nhau bởi dấu cách (~1<= X < Y <= 10^9~)

Kết quả ra: Ghi vào tệp văn bản CPP.OUT số lượng các số chính phương tìm được.

Ví dụ

Input: CPP.INP

2 10

Output: CPP.OUT

2

SEA Games 31 có tổ chức nội dung thi bắn cung tên. Ban tổ chức đã chuẩn bị rất nhiều các mục tiêu để bắn, các mục tiêu được đánh số bắt đầu từ ~1~. Có ~N~ cung thủ đang bắn tên vào các mục tiêu đó. Cung thủ thứ ~i~ bắn trúng vào tất cả các mục tiêu là bội số của ~k_i~.

Yêu cầu

Hãy tìm mục tiêu có giá trị nhỏ nhất mà tất cả các cung thủ đều bắn trúng.

Input

• Dòng đầu tiên chứa số ~N~ là số lượng cung thủ ~(1 \le N \le 15)~.
• Dòng tiếp theo chứa ~N~ số nguyên dương ~k_1, k_2, k_3, ..., k_N~, trong đó số thứ ~i~ biểu thị giá trị ki của cung thủ thứ ~i~ ~(1 \le k_i \le 48)~;

Output

• Một số nguyên duy nhất là đáp án của bài toán.

Scoring

• Không có giới hạn gì thêm

Ví dụ

Input

3
2 3 4

Output

12

Tèo đang chuẩn bị tiết học thủ công, cậu ta có ~n~ thẻ tre ~a_1, a_2,...,a_n~ với thẻ tre thứ ~i~ có độ dài ~a_i~ (đơn vị độ dài). Tèo sẽ lấy các thẻ tre có độ dài bằng nhau để tạo thành các hình tam giác đều riêng biệt (các thẻ tre không bị cắt bỏ mà giữ nguyên chiều dài ban đầu). Số còn lại Tèo sẽ cho Tí làm đồ chơi.

Yêu cầu

Cho ~n~ thẻ tre với thẻ thứ ~i~ có độ dài ~a_i~ (đơn vị độ dài). Tính số lượng tam giác đều tối đa mà Tèo có thể tạo thành và số lượng thẻ tre còn lại mà Tèo sẽ cho Tí?

Input

• Dòng đầu tiên chứa số nguyên dương ~n~ là số lượng thẻ tre mà Tèo có ~(1 \le n \le 10^6)~.
• Dòng thứ hai chứa ~n~ số nguyên dương ~a_1, a_2, a_3,..., a_n~ ghi cách nhau bởi dấu cách với ~a_i~ là độ dài của thẻ tre thứ ~i~ ~(1\le a_i \le 2000)~.

Output

• Gồm hai số nguyên dương ~x~ và ~y~ ghi cách nhau bởi dấu cách, với ~x~ là số lượng tam giác đều tối đa mà Tèo tạo được, ~y~ là số thẻ tre Tèo sẽ cho Tí.

Scoring

• Không có giới hạn gì thêm

Ví dụ

Input

8
1 2 6 6 1 1 2 1

Output

1 5

Khách sạn XYZ là nơi đón tiếp các đoàn thể thao về nghỉ ngơi trong SEA Games 31. Sau mỗi bữa ăn, khách sạn sẽ phải rửa dọn rất nhiều chiếc đĩa. Nam là người chịu trách nhiệm rửa sạch và xếp chúng lên nhau. Nam có ~n~ chiếc đĩa được đánh số từ ~1~ tới ~n~. Những chiếc đĩa có độ bền lần lượt là ~a_1, a_2, ..., a_n~. Một chiếc đĩa có độ bền ~a_i~ nghĩa là Nam có thể xếp lên trên đĩa đó tối đa ~a_i~ chiếc đĩa khác, nếu xếp lên nhiều hơn thì đĩa đó sẽ bị vỡ.

Yêu cầu

Hãy cho biết số đĩa tối đa mà Nam có thể xếp được sao cho đĩa không bị vỡ.

Input

• Dòng thứ nhất chứa số nguyên dương ~n~ ~(1 \le n \le 10^5)~ là số lượng đĩa.
• Dòng thứ hai gồm ~n~ số nguyên ~a_1, a_2, ..., a_n~ với ~a_i~ là độ bền của chiếc đĩa thứ ~i~ ~(0 \le a_i \le 10^9)~. Các số trên một dòng ghi cách nhau bởi dấu cách.

Output

• Một số nguyên duy nhất là đáp án của bài toán

Scoring

• Không có giới hạn gì thêm

Ví dụ

Input

3
1 2 1

Output

3

Giải thích ví dụ

• Chồng đĩa cao nhất được xếp với 3 đĩa theo thứ tự từ dưới lên trên là đĩa thứ 2, đĩa thứ 1 rồi đến đĩa thứ 3.