Vào một ngày "đẹp trời", Maowonh đang đi dạo ngó ngơ lung tung thì đụng phải 1 bạn chuyên Toán (tên gì chắc các bạn cũng biết). Để xin lỗi bạn ấy thì Maowonh buộc phải giải quyết bài toán sau:

Cho 1 số \(k\) , hãy tìm vị trí xuất hiện đầu tiên của \(2^k\) trong khoảng \(2^L\) đến \(2^R\) dưới dạng là kết quá của 1 phép tính \(2^i \mod 10^x\) với \(x\) là độ dài (số chữ số) của \(2^k\) và \(i\) là vị trí sao cho kết quả bằng \(2^k\)

Maowonh thấy bài toán này rất hay nên quyết định viết đề khó hơn để đố các bạn nhằm qua cơn buồn chán của mùa dịch:

Đố các bạn phải trả lời \(T\) câu hỏi của bài toán trên

Input

• Dòng đầu tiên là số \(T\), số lượng câu hỏi \((1 \le T \le 10^5)\)

• \(T\) dòng tiếp theo, mỗi dòng chứa 3 số \(k\), \(L\), \(R\) \((1 \le k \le 30 ;k < L < R \le 10^{18} )\)

Output

• Gồm \(T\) dòng, mỗi dòng là kết quả của mỗi câu hỏi trên

Example

6
1 3 5
2 4 1000
1 8 10000000000 
3 5 1234567890123
9 13881 194021904812908
20 13849317481 913048398130130949 

5
6
9
7
13909
13849375020