Để tránh việc 1 gói tin sẽ di chuyển lòng vòng trên mạng, người ta đưa ra 1 giới hạn gọi thời Thời gian sống (TGS). Thời gian sống cho biết số lượng nút là gói tin có thể đi qua (không tính nút xuất phát) trước khi bị hủy.

Ví dụ, với mạng cục bộ như hình bên dưới thì nếu TGS là 2, gói tin xuất phát từ nút 35 sẽ có thể đến nút 15, 10, 55, 50, 40, 20, 60 và không thể đến nút 30, 47, 25, 45, 65.

Input: Gồm nhiều bộ test.

Mỗi bộ test là 1 mạng cục bộ bắt đầu bởi số nguyên dương $n$ cho biết số lượng kết nối giữa những nút trong mạng.

Theo sau là $n$ cặp số nguyên dương, mỗi cặp số nguyên dương là "tên" 2 nút mà giữa chúng có 1 kết nối. Mỗi mạng có tối đa $30$ nút.

Với mỗi mạng sẽ có nhiều câu hỏi.

Mỗi câu hỏi là 1 cặp số nguyên. Số thứ nhất là "tên" nút bắt đầu và số thứ hai là TGS. Các câu hỏi kết thúc khi gặp cặp số $0$ $0$.

Input kết thúc khi $n$ bằng $0$.

Output: Với mỗi câu hỏi, hiển thị số lượng nút mà gói tin không thể đến trong câu hỏi đó trên 1 dòng.

Input mẫu

16
10 15 15 20 20 25 10 30 30 47 47 50 25 45 45 65
15 35 35 55 20 40 50 55 35 40 55 60 40 60 60 65
35 2 35 3 0 0
14
1 2 2 7 1 3 3 4 3 5 5 10 5 11
4 6 7 6 7 8 7 9 8 9 8 6 6 11
1 1 1 2 3 2 3 3 0 0
0

Output mẫu

5
1
8
5
3
1