Hôm nay, lớp của Quân làm bài tập môn Toán về nội dung đưa thừa số ra ngoài dấu căn. Bằng kiến thức đã học Quân biết rằng với mọi số tự nhiên ~a > 0~ luôn luôn phân tích được dưới dạng ~\sqrt{a}=\sqrt{x^2\times y}=x\sqrt{y}~ với ~x~ gọi là phần nguyên, ~y~ gọi là phần dưới dấu căn (~x, y~ nguyên dương).

Ví dụ: ~\sqrt{8}=\sqrt{2^2\times 2}=2\sqrt{2}~; ~\sqrt{1}=\sqrt{1^2\times 7}=1\sqrt{7}~; ~\sqrt{4}=\sqrt{2^2\times 1}=2\sqrt{1}~

Em hãy viết chương trình giúp Quân giải quyết bài toán.

Yêu cầu: Đưa ra phần nguyên ~x~ và phần dưới dấu căn ~y~ của ~\sqrt{a}~.

Input

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

Output

• Ghi ra ~n~ dòng, mỗi dòng chứa hai số nguyên dương thỏa mãn yêu cầu bài toán.

Sample Input

2
18 
4

Sample Output

3 2
2 1

Sample Input

2
7
8

Sample Output

1 7
2 2

Subtasks:

• 60% số test với ~1 \le N \le 10^2; 1 \le a \le 10^4~
• 30% số test với ~10^2 < N \le 10^3; 10^4 < a \le 10^6~
• 10% số test với ~10^2 < N \le 10^3; 10^6 < a \le 10^9~

Bạn Nguyên rất yêu thích môn Toán. Trong lúc giải các bài toán về số học, bạn ấy phát hiện ra các số mà mình tìm được có nhiều số đặc biệt với đặc điểm là chỉ có 3 ước số nguyên dương khác nhau. Bạn Nguyên đặt tên cho các số này là số T - Nguyên tố.

Yêu cầu: hãy lập trình giúp bạn Nguyên đếm xem có bao nhiêu số T - Nguyên Tố có giá trị không vượt quá số nguyên dương ~N~ cho trước

Input

• Một dòng chứa số nguyên dương ~N\ (2 \le N \le 10^9)~.

Output

• Ghi ra số lượng số T - Nguyên tố tìm được.

Sample Input

6

Sample Output

1

Subtasks:

• 80% số test với ~1 \le N \le 10^6~
• 20% số test với ~10^6 < N \le 10^9~

Do tình hình Covid-19 diễn biết phức tạp, Ban chỉ đạo Phòng chống dịch tỉnh ~X~ tổ chức diễn tập phòng chống dịch, với kế hoạch trưng dụng một số khách sạn để làm khu cách ly tập trung cho các F1, là nhũng người tiếp xúc gần với bệnh nhân F0. Để dự trù số phòng trước khi cách ly chính thức, Ban chỉ đạo thực hiện:

• Phân các F1 thành ~N~ nhóm nhỏ theo thời gian phát hiện, mỗi nhóm không quá 4 người;
• Bố trí các nhóm vào chung phòng, mỗi phòng không quá 4 người;
• Các F1 trong một nhóm phải ở chung một phòng.

Yêu cầu: Cần sử dụng ít nhất bao nhiêu phòng để bố trí cách ly các nhóm trên

Input

• Dòng thứ nhất chứa số nguyên ~N~ là số lượng nhóm F1 ~(1 \le N \le 10^4)~
• Dòng thứ hai chứa ~N~ số nguyên ~a_1, a_2, ..., a_N\ (1\le a_i\le 4)~ tương ứng với số F1 trong mỗi nhóm.

Output

• Ghi ra số nguyên là số lượng phòng ít nhất cần sử dụng để cách ly.

Sample Input

5
1 2 4 3 3

Sample Output

4 

Sample Input

4
4 3 3 2

Sample Output

4 

Subtasks

• 60% số test với ~1 \le N \le 10^2~
• 40% số test với ~10^2 < N \le 10^4~

Trong giải bóng đá vòng loại World Cup 2022, khán giả khi mua vé sẽ được Ban tổ chức đánh số thứ tự từ ~1, 2,..., N~; trên vé của khán giả thứ ~i~ chứa một số ngẫu nhiên ~a_i~ là mã số vé. Sau mỗi trận đấu, Ban tổ chức thực hiện trao thưởng cho cặp khán giả may mắn. Cặp khán giả ở vị trí thứ ~i~ và vị trí thứ ~j~ được gọi là may mắn nếu thỏa mãn các điêu kiện sau:

• ~1\le i < j \le N~
• ~a_j-a_i \ge p~ với ~p~ là số ngẫu nhiên do Ban tổ chức đưa ra.
• ~j-i~ lớn nhất.

Yêu cầu: Đưa ra vị trí cặp khán giả may mắn

Input

• Dòng thứ nhất chứa hai số nguyên ~N~ và ~p~ ~(1 \le N\le 10^6, 0 < p \le 10^6)~.
• Dòng thứ hai chứa ~N~ số nguyên ~a_1, a_2, ..., a_N\ (1\le a_i\le 10^9)~

Output

• Ghi ra hai số nguyên dương là vị trí của cặp khán giả may mắn. Nếu có nhiều cặp thỏa mãn yêu cầu bài toán thì đưa ra vị trí cặp may mắn đầu tiên, nếu không có thì ghi kết quả bằng 0.

Sample Input

6 3
4 3 7 2 6 4

Sample Output

2 5 

Sample Input

7 3
1 2 2 2 3 3 3

Sample Output

0

Sample Input

6 3
3 7 2 6 4 5

Sample Output

1 4

Subtasks:

• 50% số test với ~1 \le N \le 10^2~
• 25% số test với ~10^2 < N \le 10^4~
• 25% số test với ~10^4 < N \le 10^6~