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 đố, ~1 \le T \le 100~. Mỗi câu đố cho hai số nguyên ~0 \le L \le R \le 10^{100000}~, yêu cầu tìm số lượng 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 subtask\_id \le 4~) và số lượng câu đố ~T~ (~1 \le T \le 10~).

• ~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.

Scoring

Sample Input 1

1 2
0 20
36 67

Sample Output 1

6
9

Notes

Các số tự nhiên ~x~ thỏa mãn ở câu đố thứ nhất là ~2, 4, 5, 6, 10, 15~ và ở câu đố thứ hai là ~36, 44, 46, 47, 48, 52, 57, 65, 67~.