Lam đặt tên các biến trong mã nguồn chương trình của mình theo chuẩn PropCase. Chuẩn PropCase quy ước như sau:

• Tên biến gồm các chữ cái latinh 'A'...'Z', 'a'...'z', và chữ số '0'...'9'.
• Chữ cái đâu tiên của biến không bắt đầu bằng chữ số '0'...'9'.
• Chữ cái đầu tiên của mỗi từ tiếp theo trong tên biến được viết in hoa
• Ví dụ: DiemTbHk1, lop9A10, ...

Lam muốn tải mã nguồn của mình lên Github với các biến được đặt tên theo chuẩn join_case có quy ước:

• Tên biến gồm các chữ cái Latinh 'a'...'z', chữ số '0'...'9' và dấu gạch nối '_'
• Không bắt đầu bằng chữ số '0'...'9' và dấu gạch nối '_'
• Hai từ trong tên biến được tách nhau bởi dấu '_'
• Ví dụ: diemtbhk1, lop9_a10, ...

Yêu cầu: Hãy giúp Lam biến đổi từ tên biến chuẩn PropCase sang chuẩn join_case.

Input

Gồm một xâu độ dài n (~1 \le n \le 1000~) là một tên biến đặt theo chuẩn ProCase

Output

Ghi ra một xâu là tên biến đặt theo chuẩn join_case

Ví dụ

Sample Input 1

DiemTbHk1

Sample Output 1

diem_tb_hk1

Sample Input 2

lop9A10

Sample Output 2

lop9_a10

Đếm số cách mua một con gà và một con chó sao cho tổng số tiền phải trả để mua cả hai con không vượt quá ~n~.

Biết rằng số tiền mua gà luôn nhỏ hơn số tiền mua chó. Số tiền mua gà và chó đều là số nguyên dương

Input

• Gồm một số nguyên dương ~n~

Output

• Ghi ra một số nguyên duy nhất là số cách mua hợp lệ

Ràng buộc

• ~3 \le n \le 2 \times 10^9~

Phân nhóm test:

• 70% số test ứng với ~n \le 10^3~
• 20% số test ứng với ~n \le 10^6~
• 10% số test ứng với ~n \le 2 \times 10^9~

Ví dụ

Sample Input

5

Sample Output

4

Một số tự nhiên được gọi là đối xứng nếu viết các chữ số của nó theo chiều ngược lại thì vẫn thu được chính nó. Ví dụ, các số 88, 858 là những số đối xứng.

Một số được coi là số đặc biệt nếu nó là số đối xứng và có từ 3 ước số nguyên tố khác nhau trở lên. Ví dụ, số 858 là số đặc biệt vì nó là số đối xứng và có 4 ước nguyên tố khác nhau là 2, 3, 11, 13; còn số 88 không là số đặc biệt vì nó đối xứng nhưng chỉ có 2 ước nguyên tố khác nhau là 2, 11.

Yêu cầu: Cho hai số nguyên dương a và b. Hãy tính tổng các số đặc biệt trong đoạn từ a đến b (bao gồm cả a và b).

Input

Gồm hai số nguyên dương a, b (1 ≤ a ≤ b).

Output

Gồm một số duy nhất là tổng các số đặc biệt trong đoạn từ a đến b.

Sample Input

88 858

Sample Output

11605

Ràng buộc

• Có 60% số test ứng với 1 ≤ a < b ≤ 10^7
• Có 20% số test ứng với 1 ≤ a < b ≤ 10^3
• Có 20% số test ứng với 10^3 < a < b ≤ 10^6

Trên cùng một mặt phẳng tọa độ, cho n đường thẳng phân biệt được đánh số từ 1 đến n. Mỗi đường thẳng có dạng: ~y = a_i x + b_i~

Yêu cầu: Đếm số cặp đường thẳng song song trong n đường thẳng đã cho.

Input

• Dòng đầu tiên là số nguyên n — số lượng đường thẳng.
• n dòng tiếp theo, mỗi dòng ghi hai số nguyên a_i, b_i biểu diễn đường thẳng thứ i.

Output

• Ghi ra một số nguyên duy nhất là số cặp đường thẳng song song.

Ràng buộc

• ~2 \le n \le 3 \times 10^6~
• ~|a_i|, |b_i| \le 10^9~

Ví dụ 1

Input

3
1 2
1 -2
0 2

Output

1

Giải thích

Chỉ có một cặp đường thẳng có cùng hệ số góc là a = 1.

Ví dụ 2

Input

3
1 2
1 -2
1 -4

Output

3

Giải thích

Cả ba đường thẳng đều có cùng hệ số góc a = 1, nên có ~C(3,2) = 3~ cặp song song.