Trong trung tâm nghiên cứu năng lượng số học, mỗi tinh thể được gán một mức năng lượng là số nguyên dương ~a_i~.

Hai tinh thể được xem là cộng hưởng hoàn hảo nếu tổng năng lượng của chúng chia hết cho 3.

Nhiệm vụ của bạn là đếm số lượng cặp tinh thể thỏa mãn điều kiện trên.

Cụ thể, hãy đếm số cặp chỉ số ~(i, j)~ sao cho:

• ~1 ≤ i < j ≤ n~
• ~a_i + a_j~ chia hết cho ~3~.

Dữ liệu vào

• Dòng đầu chứa số nguyên dương n — số lượng tinh thể (~1 < n \le 10^6~).
• Dòng thứ hai chứa ~n~ số nguyên dương ~a_i~ (~1 \le a_i \le 10^6, 1 \le i \le n~).

Dữ liệu ra

In ra một số nguyên duy nhất — số lượng cặp ~(i, j)~ thỏa mãn yêu cầu.

Ví dụ

Input

5
1 2 3 4 5

Output

4

Ràng buộc

• Subtask 1 (60% số điểm): ~n \le 10^3~

• Subtask 2 (40% số điểm): ~n \le 10^6~

Trong một trò chơi săn kho báu số học, mỗi chiếc rương được đánh số bằng một số nguyên dương. Hệ thống sẽ mở cổng bí mật nếu số lượng số nguyên tố trong đoạn đánh số từ A đến B đạt yêu cầu.

Nhiệm vụ của bạn là xác định có bao nhiêu số nguyên tố nằm trong đoạn [A, B].

Định nghĩa

Một số nguyên tố là số nguyên dương lớn hơn 1 và chỉ có đúng hai ước số dương là 1 và chính nó.

Dữ liệu vào

Gồm một dòng duy nhất chứa hai số nguyên dương A và B.

~1 \le A \le B \le 10^7~

Dữ liệu ra

In ra một số nguyên duy nhất là số lượng số nguyên tố thuộc đoạn [A, B].

Ví dụ

Input

1 10

Output

4

Giải thích

Các số nguyên tố trong đoạn là: 2, 3, 5, 7.

Ví dụ 2

Input

10 20

Output

4

Giải thích

Các số nguyên tố là: 11, 13, 17, 19.

Ví dụ 3

Input

1 1

Output

0

Nhà khảo cổ Mina tìm được một viên đá cổ mang số hiệu N. Theo truyền thuyết, sức mạnh của viên đá được xác định bởi:

• ~σ(N)~: tổng tất cả các ước số dương của N,
• và độ cộng hưởng giữa viên đá với chính nó là ~GCD(N, σ(N))~.

Hãy giúp Mina tính hai giá trị này.

Dữ liệu vào

Gồm một dòng duy nhất chứa số nguyên dương N.

~1 \le N \le 10^{12}~

Dữ liệu ra

Gồm hai dòng:

• Dòng 1: giá trị ~σ(N)~ — tổng các ước số dương của N.
• Dòng 2: giá trị ~GCD(N, σ(N))~.

Ví dụ 1

Input

6

Output

12
6

Giải thích

Các ước của 6 là: 1, 2, 3, 6.

Tổng: ~\sigma(6)=1+2+3+6=12~

Do đó: ~\gcd(6,12)=6~

Ví dụ 2

Input

12

Output

28
4

Một phòng thí nghiệm số học đã chế tạo cỗ máy đặc biệt có khả năng tách một số nguyên thành các thừa số nguyên tố.

Cho số nguyên dương N, hãy phân tích N thành tích các thừa số nguyên tố theo thứ tự tăng dần.

• Nếu N là số nguyên tố, in:

N la so nguyen to

Dữ liệu vào

Gồm một dòng duy nhất chứa số nguyên N.

~2 \le N \le 10^9~

Dữ liệu ra

In kết quả theo định dạng:

p1^a1 x p2^a2 x ...

Trong đó:

• ~p1 < p2 < ...~ là các thừa số nguyên tố của N,
• ~ai~ là số mũ tương ứng.

Nếu N là số nguyên tố thì in:

N la so nguyen to

Ví dụ 1

Input

12

Output

2^2 x 3^1

Giải thích

~12=2^2\times3^1~

Ví dụ 2

Input

100

Output

2^2 x 5^2

Ví dụ 3

Input

7

Output

7 la so nguyen to

Một hệ thống năng lượng gồm N lõi sức mạnh, lõi thứ i có mức năng lượng ~a_i~.

Để hệ thống hoạt động ổn định, người ta xác định:

• G là ước chung lớn nhất của toàn bộ các lõi,
• đồng thời cần biết có bao nhiêu lõi có mức năng lượng chia hết cho G.

Hãy tính hai giá trị trên.

Dữ liệu vào

• Dòng đầu chứa số nguyên N.
• Dòng thứ hai chứa N số nguyên dương ~a_i~.

~1 \le N \le 10^5~

~1 \le a_i \le 10^9~

Dữ liệu ra

Gồm hai dòng:

• Dòng 1: giá trị G.
• Dòng 2: số lượng phần tử chia hết cho G.

Ví dụ 1

Input

4
6 12 18 24

Output

6
4

Giải thích

~\gcd(6,12,18,24)=6~

Cả 4 số đều chia hết cho 6.

Ví dụ 2

Input

3
4 6 9

Output

1
3

Ví dụ 3

Input

3
6 12 15

Output

3
3

Trong thế giới Arcadia, mỗi viên tinh thể năng lượng được đánh số bằng một số nguyên dương. Các nhà khoa học phát hiện rằng chỉ những viên mang năng lượng thuần khiết mới có thể kích hoạt cổng dịch chuyển.

Một số được gọi là số tốt nếu đồng thời thỏa mãn:

• Nó là số chính phương.
• Căn bậc hai của nó là một số nguyên tố.

Ví dụ:

• 49 là số tốt vì: ~49=7^2~ và 7 là số nguyên tố.

• 36 không phải số tốt vì: ~36=6^2~ nhưng 6 không phải số nguyên tố.

Bạn được cung cấp một dãy gồm N số nguyên dương. Hãy đếm xem trong dãy có bao nhiêu số tốt.

Dữ liệu vào

• Dòng đầu chứa số nguyên N — số lượng phần tử trong dãy.
• Dòng thứ hai chứa N số nguyên dương ~a_i~.

~1 \le N \le 10^5~

~1 \le a_i \le 10^9~

Dữ liệu ra

In ra một số nguyên duy nhất — số lượng số tốt xuất hiện trong dãy.

Ví dụ 1

Input

5
4 9 16 25 49

Output

4

Giải thích

Các số tốt là:

• ~4 = 2²~
• ~9 = 3²~
• ~25 = 5²~
• ~49 = 7²~

Trong khi:

• ~16 = 4²~ nhưng 4 không phải số nguyên tố.

Ví dụ 2

Input

6
1 8 10 27 36 121

Output

1