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\).