Kiên đang đi du lịch trên hòn đảo cá nhân của Khôi Anh. Ở giữa hòn đảo có một ngôi đền trông rất đẹp, Kiên rất mong muốn được vào tham quan nhưng ngay trước cổng vào có \(T\) câu đố. Mỗi câu đố cho hai số nguyên \(0 \le L \le R \le 10^{100000}\), yêu cầu tìm số số tự nhiên \(x\) thỏa mãn \(2^x\) có cùng số dư với \(x^2\) khi chia cho \(7\) và \(L \le x \le R\).

Tuy nhiên, Kiên lại không giỏi trong việc giải những câu đố nên nhờ bạn giúp. Bạn hãy giúp Kiên nhé.

Input

• Dòng đầu tiên gồm \(2\) số nguyên dương subtask_id (\(1 \le \text{subtask\_id} \le 4\)) và số lượng câu đố \(T\) (\(1 \le T \le 100\)).
• \(T\) dòng tiếp theo mỗi dòng gồm \(2\) số tự nhiên \(L, R\) (\(0 \le L \le R \le 10^{100000}\)).

Output

• In ra \(T\) dòng, mỗi dòng gồm \(1\) số nguyên là số lượng giá trị \(x\) thỏa mãn điều kiện của câu đố tương ứng.

Example

1 2
0 20
36 67

6
9

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(0 \le L \le R \le 10^5\).
• Subtask \(2\) (\(20\%\) số điểm): \(0 \le L \le R \le 10^{18}\) và \(R - L + 1 \le 10^5\).
• Subtask \(3\) (\(50\%\) số điểm): \(0 \le L \le R \le 10^{18}\).
• Subtask \(4\) (\(10\%\) số điểm): \(0 \le L \le R \le 10^{100000}\).