Cho một cây gồm $N$ đỉnh được đánh số từ $1$ đến $N$. Với mỗi đỉnh $i$ $(2\le i\le N)$ tồn tại đúng một cạnh nối $i$ và $\left\lfloor\dfrac{i}{2}\right\rfloor$. Ta định nghĩa khoảng cách từ đỉnh $u$ đến đỉnh $v$ trên cây (và ngược lại) bằng đúng số lượng cạnh xuất hiện trên đường đi duy nhất từ $u$ đến $v$.

Cho biết hai số nguyên $X$ và $K$ $(1\le X\le N, 0\le K\le N-1)$, bạn hãy viết chương trình xác định có bao nhiêu đỉnh trên cây có khoảng cách đến $X$ đúng bằng $K$.

Input

• Dòng đầu chứa số nguyên dương $T$ thể hiện số lượng câu hỏi $\left(T\le 10^5\right)$.
• Trong $T$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $N$, $X$, $K$ $\left(1\le N\le 10^{18}, 1\le X\le N, 0\le K\le N-1\right)$.

Output

• Gồm $T$ dòng là câu trả lời cho từng câu hỏi tương ứng.

Ví dụ

Sample input 01

5
10 2 0
10 2 1
10 2 2
10 2 3
10 2 4

Sample output 01

1
3
4
2
0

Giải thích

• Tập các đỉnh có khoảng cách tới đỉnh $2$ bằng $0$ là: $\{2\}$.
• Tập các đỉnh có khoảng cách tới đỉnh $2$ bằng $1$ là: $\{1,4,5\}$.
• Tập các đỉnh có khoảng cách tới đỉnh $2$ bằng $2$ là: $\{3,8,9,10\}$.
• Tập các đỉnh có khoảng cách tới đỉnh $2$ bằng $3$ là: $\{6,7\}$.
• Không có đỉnh nào có khoảng cách tới đỉnh $2$ bằng $4$.