Hôm nay HCN nhập được n bài vào contest. Mỗi bài có 2 chỉ số ai là chủ đề của bài và bi là độ khó, tất cả các bài đều khác nhau, nghĩa là không có 2 bài bất kì nào đều có cùng chủ đề và độ khó. HCN cần chọn ra 3 bài thỏa mãn ít nhất 1 trong 2 điều kiện sau:

• Chủ đề của 3 bài khác nhau.

• Độ khó của 3 bài khác nhau.

Hãy đếm số cách để HCN có thể chọn ra 3 bài như vậy.

Input:

• Dòng đầu tiên gồm số nguyên không âm 3 ≤ n ≤ 10^5.

• n dòng tiếp theo mỗi dòng gồm 2 số 1 ≤ ai, bi ≤ n.

Output: Hãy in ra số cách chọn.

Sample Test

Input:

4
2 4
3 4
2 1
1 3

Output:

3

Input:

5
1 5
2 4
3 3
4 2
5 1

Output:

10

Mô tả: Cho mảng A. Đếm số cách chia mảng thành 3 đoạn liên tiếp khác rỗng sao cho tổng các phần tử của 3 đoạn bằng nhau.

Input:

Dòng 1: N (1 ≤ N ≤ 5. 10^5).

Dòng 2: Ai (|A¡| ≤ 10^9).

Output: Số cách chia.

Input:

5
1 2 3 0 3

Output:

2

Có N loại đồ vật, loại thứ i có trọng lượng W[i] và giá trị V[i]. Số lượng đồ vật mỗi loại là vô hạn. Túi của bạn chịu được trọng lượng tối đa M. Hãy tìm tổng giá trị lớn nhất.

Dữ liệu vào:

Dòng 1: N và M (1 <= N <= 100, 1 <= M <= 10^4).

N dòng tiếp theo: Mỗi dòng chứa W[i] và V[i].

Dữ liệu ra:

Giá trị lớn nhất.

Ví dụ:

Input:

2 10 
2 5 
4 8

Output:

25

Cho Q truy vấn. Mỗi truy vấn là số N. Hãy đếm số lượng ước nguyên tố phân biệt của N (ký hiệu là omega(N)).

Dữ liệu vào:

Dòng 1: Q (1 <= Q <= 10^6).

Q dòng tiếp theo: N (1 <= N <= 10^7).

Dữ liệu ra:

Kết quả mỗi truy vấn.

Ví dụ:

Input:

2 
12 
30

Output:

2 
3

Giải thích: 12 = 2^2 * 3 (có 2 ước NT là 2, 3). 30 = 235 (có 3 ước NT).

Cho số nguyên dương N. Hãy tìm số nguyên dương K lớn nhất sao cho K * K <= N. (Đây chính là phần nguyên của căn bậc hai của N).

Dữ liệu vào:

Một số nguyên dương N.

Dữ liệu ra:

Số nguyên K tìm được.

Giới hạn:

1 <= N <= 10^18

Ví dụ:

Input:

20

Output:

4