Trường THPT A chia quà tết cho các học sinh thuộc diện chính sách dịp cuối năm 2020, có ~X~ chiếc áo và ~Y~ hộp bánh. Một phương án chia quà của nhà trường là chọn ra ~N~ học sinh được nhận quà sao cho có thể chia hết ~X~ chiếc áo và ~Y~ hộp bánh, đồng thời mỗi học sinh sẽ nhận được số lượng chiếc áo bằng nhau và số lượng hộp bánh cũng bằng nhau.

Yêu cầu: Tìm tất cả các phương án chia quà thoả mãn điều kiện nêu trên. Giả sử rằng số học sinh thuộc diện chính sách của nhà trường là đủ nhiều để có thể thực hiện được tất cả các phương án chia quà.

Input

Đọc từ tệp CAU1.INP – gồm ~2~ số nguyên dương ~X, Y~ (~X, Y \le 10^9~).

Output

Ghi ra tệp CAU1.OUT một số nguyên là số phương án chia quà tìm được.

Scoring

Sample Input 1

6 18

Sample Output 1

4

Sample Input 2

12 8

Sample Output 2

3

Trong máy tính, một bức ảnh có các điểm ảnh, mỗi điểm ảnh được biểu thị bởi một màu, có thể có những điểm ảnh có màu giống nhau, mỗi màu được quy định bằng một mã màu, mã màu là một số nguyên dương có giá trị không quá ~10^6~.

Yêu cầu: Cho trước một bức ảnh có ~N~ điểm ảnh và mã màu của từng điểm ảnh. Hãy cho biết số lượng điểm ảnh có mã màu giống nhau nhiều nhất.

Input

Đọc từ tệp CAU2.INP gồm hai dòng:

• Dòng thứ nhất ghi số nguyên dương ~N~ (~N \le 10^6~)

• Dòng thứ hai ghi ~N~ số nguyên dương ~a_1, a_2, \dots, a_N~ với ~a_i~ là mã màu của điểm ảnh thứ ~i~ (~1 \le a_i \le 10^6~; ~i = 1..N~).

Output

Ghi ra tệp CAU2.OUT một số nguyên là kết quả tìm được

Scoring

Sample Input 1

8
1 9 2 9 3 1 1 9

Sample Output 1

3

Cho số tự nhiên ~N~. Bằng cách giữ nguyên hoặc xoá đi một số chữ số liên tiếp của ~N~ (nhưng không xoá hết) ta nhận được một số mới, nếu số ~N~ bị chia thành ~2~ phần thì số mới được ghép lại từ hai phần này và giữ nguyên trật tự.

Yêu cầu: Hãy xác định tất cả số cách xoá như trên để số ~N~ mới sau khi xoá chia hết cho ~3~. Lưu ý là hai vị trí khác nhau sẽ tạo ra hai cách xoá khác nhau. Số ~N~ giữ nguyên cũng được coi là một cách xoá.

Input

Đọc từ tệp CAU3.INP chứa số nguyên dương ~N~ (không quá ~10^5~ chữ số)

Output

Ghi ra tệp CAU3.OUT một số nguyên là số cách xoá tìm được

Scoring

Subtask	Điểm	Giới hạn
1	~50\%~	Số các chữ số của ~N \le 300~
2	~25\%~	Số các chữ số của ~N \le 10^4~
3	~25\%~	Số các chữ số của ~N \le 10^5~

Sample Input 1

1005

Sample Output 1

4

Sample Input 2

2009

Sample Output 2

3

Muốn cải thiện vốn từ vựng tiếng Anh của mình thông qua trò chơi nhận diện từ, Quyên tự viết ra một xâu ~S~ có độ dài không quá ~10^6~ chỉ gồm các kí tự thường trong bảng chữ cái tiếng Anh. Từ đó, Quyên tìm ra tất cả các từ vựng có trong ~S~. Một từ vựng sẽ thu được bằng cách ghép một số kí tự liên tiếp lấy từ ~S~, giữ nguyên trật tự của chúng, thoả mãn một trong hai điều kiện sau:

• Bắt đầu bằng một nguyên âm (là các chữ cái: a, e, i, o, u) và kết thúc bằng một phụ âm (là các chữ cái còn lại)

• Bắt đầu bằng một phụ âm và kết thúc bằng một nguyên âm

Yêu cầu: Hãy giúp Quyên đếm số lượng từ vựng có trong ~S~ theo quy tắc trên

Input

Đọc từ tệp CAU4.INP gồm xâu ~S~ không quá ~10^6~ kí tự.

Output

Ghi ra tệp CAU4.OUT một số nguyên là kết quả tìm được.

Sample Input 1

adceba

Sample Output 1

9

Notes

Subtask	Điểm	Giới hạn
1	~\frac{1}{3}~	Độ dài xâu ~S~ không quá ~10^4~
2	~\frac{2}{3}~	Không có ràng buộc gì thêm

Hiền có ~N~ que tính, mỗi que có độ dài là một số nguyên dương và đôi một khác nhau. Hiền muốn tạo ra các tam giác bằng cách ghép ba que tính với nhau, độ dài mỗi cạnh của tam giác đúng bằng độ dài của một que tính.

Yêu cầu: Giúp Hiền tính xem có thể tạo được bao nhiêu tam giác nhọn, tam giác vuông và tam giác tù khác nhau từ các que tính này. Hai tam giác được gọi là khác nhau nếu có ít nhất một que tính khác nhau.

Input

Đọc từ tệp CAU5.INP gồm:

• Dòng đầu tiên là số lượng que tính ~N~ (~3 \le N \le 5000~).

• Dòng thứ hai gồm ~N~ số nguyên dương không lớn hơn ~10^4~ là chiều dài của ~N~ que tính.

Output

Ghi ra tệp CAU5.OUT một dòng duy nhất gồm ~3~ số nguyên lần lượt là số lượng tam giác nhọn, tam giác vuông và tam giác tù tạo được.

Scoring

Subtask	Điểm	Giới hạn
1	~25\%~	~3 \le N \le 300~
2	~75\%~	Không có ràng buộc gì thêm

Sample Input 1

6
2 12 9 10 3 15

Sample Output 1

2 1 4