SUFFIXPOW2

Xem PDF



Tác giả:
Dạng bài
Điểm: 2200 (p) Thời gian: 2.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

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

Test 1

Input
6
1 3 5
2 4 1000
1 8 10000000000 
3 5 1234567890123
9 13881 194021904812908
20 13849317481 913048398130130949 
Output
5
6
9
7
13909
13849375020

Bình luận


  • 0
    hhoangcpascal    12:29 p.m. 17 Tháng 8, 2020

    Giả sử k = 5, L = 6, R = 7 thì xuất ra -1 akkk?


    • 0
      Maowonh    12:38 p.m. 17 Tháng 8, 2020

      bảo anh cuom viết thêm rồi mà ảnh quên


      • 0
        Maowonh    12:35 p.m. 17 Tháng 8, 2020

        yes