Trong một khu rừng nhiệt đới rộng lớn, có ~N~ loài sinh vật sinh sống và hình thành nên một chuỗi phụ thuộc sinh học.
Mỗi loài được gán một chỉ số sức sống ~A_i~ thể hiện khả năng sinh tồn của chúng,
và mỗi loài (trừ loài đầu tiên) phụ thuộc trực tiếp vào một loài khác trong chuỗi — gọi là loài mà nó lấy dinh dưỡng hoặc năng lượng từ đó.

Cụ thể:

• Loài ~1~ là loài đầu chuỗi (không phụ thuộc ai).
• Với mỗi loài ~i > 1~, giá trị ~B_i~ cho biết loài mà nó phụ thuộc trực tiếp.
  (Do đó, ~B_i < i~ để đảm bảo chuỗi phụ thuộc hợp lệ.)

Tuy nhiên, giữa các loài có thể xảy ra cạnh tranh tài nguyên:

• Nếu một loài phụ thuộc vào một loài khác có chỉ số sức sống nhỏ hơn hoặc bằng mình,
  thì hai loài này không thể cùng tồn tại trong cùng một hệ sinh thái ổn định.

Nhiệm vụ của bạn là chọn ra tập hợp lớn nhất các loài sinh vật có thể cùng tồn tại,
sao cho không có cặp "loài phụ thuộc – loài bị phụ thuộc" nào cạnh tranh tài nguyên theo quy tắc trên.

Input

• Dòng đầu chứa số nguyên dương ~N~ — số lượng loài trong khu rừng.
  ~(2 ≤ N ≤ 2×10⁵)~

• ~N~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~A_i~ và ~B_i~:

  • ~A_i~ — chỉ số sức sống của loài ~i~
  • ~B_i~ — loài mà ~i~ phụ thuộc trực tiếp (~0~ nếu là loài đầu chuỗi)
    ~(0 ≤ B_i < i, 1 ≤ A_i ≤ 10⁹)~

Output

• In ra một số nguyên duy nhất — số lượng loài tối đa có thể cùng tồn tại trong mạng sinh vật cân bằng.

Input

8
8 0
3 1
7 2
9 2
4 2
7 1
3 5
8 5

Output

6

Quốc gia K có ~N~ điệp viên, mỗi người mang số hiệu từ ~1~ đến ~N~.

• Người mang số hiệu ~1~ là lãnh đạo tối cao.
• Mỗi điệp viên ~i~ (~i > 1~) có cấp trên trực tiếp là điệp viên ~B_i~, với điều kiện ~0 < B_i < i~.
  (Điệp viên ~1~ không có cấp trên, nên ~B_1 = 0~.)
• Nếu điệp viên i là cấp trên của j, điệp viên j là cấp trên của k, thì i cũng là cấp trên của k.

Mỗi điệp viên có năng lực là ~A_i~.

Tuy nhiên, nếu một điệp viên làm cấp trên của một người có năng lực cao hơn hoặc bằng mình, cả hai sẽ bất đồng và không thể cùng làm việc trong một đội.

Tổng tư lệnh quốc gia muốn thành lập một đội siêu trinh thám, gồm nhiều điệp viên nhất có thể, sao cho không có bất kỳ cặp nào cấp trên – cấp dưới trong đội rơi vào tình trạng bất đồng.

Hãy xác định số lượng điệp viên tối đa có thể cùng làm việc trong một đội như vậy.

Input:

• Dòng đầu chứa số nguyên dương ~N~ (~2 ≤ N ≤ 2×10^5~) — số lượng điệp viên.
• ~N~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~A_i, B_i~ — năng lực và cấp trên trực tiếp của điệp viên thứ ~i~
  (~1 ≤ i ≤ N~, ~0 < A_i ≤ 10^9~, ~0 ≤ B_i < i~).
  (Với ~i = 1~, ta có ~B_1 = 0~.)

Output:

• In ra một số nguyên duy nhất — số lượng điệp viên nhiều nhất có thể cùng một đội mà không xảy ra bất đồng.

Sample Test

Input:

8
8 0
3 1
7 2
9 2
4 2
7 1
3 5
8 5

Output:

5

Giải thích:
Chọn các điệp viên ~1, 3, 5, 6, 7~.
Điệp viên ~1~ là lãnh đạo tối cao (~B_1 = 0~), và không có cặp nào cấp trên – cấp dưới có năng lực ngược quy tắc.

Giới hạn:

• Subtask 1 (20% số điểm): ~1 ≤ N ≤ 1000~
• Subtask 2 (80% số điểm): Không có giới hạn bổ sung.

Xét một số nguyên dương ~x~ gồm ~n~ chữ số, được biểu diễn dưới dạng thập phân như sau:
~x = d_n d_{n-1} ... d_2 d_1~.

Ta định nghĩa ~F(x)~ là số lượng "cặp nghịch thế" của ~x~, tức là số lượng cặp chỉ số ~(i, j)~ thỏa mãn:

• ~1 ≤ i < j ≤ n~, và
• ~d_i > d_j~.

Ví dụ:

• ~F(153) = 2~ vì có hai cặp chỉ số thỏa mãn là ~(1, 3)~ và ~(2, 3)~.
• ~F(321) = 0~ vì mọi chữ số đều không thoả điều kiện ~d_i > d_j~ khi ~i < j~.

Cho hai số nguyên dương ~l, r~ (~l ≤ r~).
Hãy tính tổng: ~sum_{x = l}^{r} F(x)~

Input:

• Dòng đầu tiên chứa một số nguyên dương ~T~ — số lượng bộ dữ liệu cần giải quyết (~T ≤ 50000~).
• ~T~ dòng tiếp theo, mỗi dòng chứa hai số nguyên dương ~l, r~ (~1 ≤ l ≤ r ≤ 10^{14}~).

Output:

• Với mỗi bộ dữ liệu, in ra một dòng chứa kết quả tương ứng.

Sample Test:

Input:

3
1 7
3 15
10 20

Output:

0
4
8

Score:

• 20% số điểm: ~r ≤ 10^6~.
• 30% số điểm: ~T ≤ 5000~.
• 50% số điểm còn lại: không có giới hạn bổ sung.