Ta đã biết rằng một đồ thị gồm hai tập: tập cạnh ~E~ và tập đỉnh ~V~. Thông thường người ta hay đặt tên các đỉnh của tập ~V~ là 1, 2, \dots nhưng Bờm thì lại không đặt như vậy, cậu ta sử dụng quy luật sau đây để đặt tên cho các đỉnh của đồ thị:

• Ban đầu, tập đỉnh ~V~ chỉ có một phần tử là 2 (~V = \{2\}~);
• Bờm tiếp tục lấy các đỉnh khác theo quy tắc: Nếu ~x~ là đỉnh của đồ thị thì ~2 \times x + 1~ và ~3 \times x~ cũng là đỉnh của đồ thị. Lưu ý tập đỉnh ~V~ mà Bờm xây dựng là vô hạn số đỉnh.

Yêu cầu: Cho ~K~ truy vấn, truy vấn thứ ~i~ gồm hai số nguyên dương ~u_i~ và ~v_i~. Hãy trả lời câu hỏi “Có bao nhiêu đỉnh thuộc tập ~V~ nằm trong đoạn ~[u_i; v_i]~ ?”

Input

• Dòng 1: Chứa một số nguyên dương ~K~ (~K \le 10^6~);
• Dòng thứ ~i~ trong ~K~ dòng sau, mỗi dòng chứa hai số nguyên dương ~u_i, v_i~ (~u_i \le v_i \le 10^7~).

Output

• Ghi ra ~K~ dòng, dòng thứ ~i~ gồm một số nguyên là số lượng đỉnh cần tìm của truy vấn thứ ~i~ (~1 \le i \le K~).

Sample Input 1

2
1 6
2 20

Sample Output 1

3
7