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} \approx 3{,}16228~.

Yêu cầu

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.

Input

Đọc dữ liệu từ CHINHPHUONG.INP gồm : 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 \le X \le Y \le 10^9~

Output

Ghi ra tệp CHINHPHUONG.OUT gồm : số lượng các số chính phương tìm được.

Subtasks

• 80% số điểm: ~X \le Y \le 10^6~.
• 20% số điểm: ~X \le Y \le 10^9~.

Sample Input

2 10

Sample Output

2

Giải thích

Từ ~2~ tới ~10~ có hai số chính phương là ~4~ và ~9~.

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ố nguyên ~N~ là số lượng cung thủ.
• Dòng tiếp theo chứa ~N~ số nguyên dương ~k_1, k_2, \ldots, k_N~.

Điều kiện:

• ~1 \le N \le 15~
• ~1 \le k_i \le 48~

Output

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

Subtasks

• 60% số điểm: ~k_i \le 20~, ~N \le 5~
• 40% số điểm: ~k_i \le 48~, ~N \le 15~

Sample Input

3
2 3 4

Sample Output

12

Giải thích

• Cung thủ thứ nhất bắn trúng các mục tiêu là bội của ~2~: ~2, 4, 6, 8, 10, 12, \ldots~
• Cung thủ thứ hai bắn trúng các mục tiêu là bội của ~3~: ~3, 6, 9, 12, 15, \ldots~
• Cung thủ thứ ba bắn trúng các mục tiêu là bội của ~4~: ~4, 8, 12, 16, \ldots~

Do đó, mục tiêu nhỏ nhất mà tất cả đều bắn trúng là ~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, \ldots, 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 Ti làm đồ chơi.

Yêu cầu

Cho ~n~ thẻ tre với thẻ thứ ~i~ có độ dài ~a_i~. Hãy tính:

• số lượng tam giác đều tối đa mà Tèo có thể tạo thành;
• số lượng thẻ tre còn lại mà Tèo sẽ cho Ti.

Input

• Dòng đầu chứa số nguyên dương ~n~ là số lượng thẻ tre Tèo có.
• Dòng thứ hai chứa ~n~ số nguyên dương ~a_1, a_2, \ldots, a_n~.

Output

Ghi ra hai số nguyên dương ~x~ và ~y~, cách nhau bởi dấu cách, trong đó:

• ~x~ là số lượng tam giác đều tối đa mà Tèo tạo được;
• ~y~ là số thẻ tre còn lại mà Tèo sẽ cho Ti.

Ràng buộc

• ~1 \le n \le 10^6~
• ~1 \le a_i \le 2000~

Subtasks

• Subtask 1 (60%): ~n \le 10^3~
• Subtask 2 (20%): ~n \le 10^5~
• Subtask 3 (20%): ~n \le 10^6~

Ví dụ

Input

8
1 2 6 6 1 1 2 1

Output

1 5

Giải thích

Các thẻ tre có độ dài:

• ~1~ xuất hiện ~4~ lần, tạo được ~\lfloor 4/3 \rfloor = 1~ tam giác, dư ~1~ thẻ;
• ~2~ xuất hiện ~2~ lần, không tạo được tam giác nào;
• ~6~ xuất hiện ~2~ lần, không tạo được tam giác nào.

Vì vậy Tèo tạo được ~1~ tam giác đều và còn lại ~5~ thẻ tre.

Khách sạn XYZ có ~n~ chiếc đĩa được đánh số từ ~1~ đến ~n~. Chiếc đĩa thứ ~i~ có độ bền ~a_i~, nghĩa là có thể chịu được tối đa ~a_i~ chiếc đĩa khác đặt lên trên nó.

Yêu cầu

Hãy tìm số lượng đĩa tối đa có thể xếp thành một chồng sao cho không có đĩa nào bị vỡ.

Input

• Dòng đầu tiên chứa số nguyên dương ~n~ là số lượng đĩa.
• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, \ldots, a_n~.

Điều kiện:

• ~1 \le n \le 10^5~
• ~0 \le a_i \le 10^9~

Output

Ghi một số nguyên duy nhất là số lượng đĩa tối đa có thể xếp được.

Subtasks

• 60% số điểm: ~n \le 10^3~
• 40% số điểm: ~n \le 10^5~

Sample Input 1

3
1 2 1

Sample Output 1

3

Giải thích 1

Có thể xếp ~3~ đĩa theo thứ tự từ dưới lên trên là các đĩa có độ bền ~2~, ~1~, ~1~.

Sample Input 2

6
0 0 0 0 0 0

Sample Output 2

1

Giải thích 2

Không có chiếc đĩa nào chịu được đĩa khác đặt lên trên, nên số đĩa tối đa trong một chồng chỉ là ~1~.