Một số nguyên không âm ~x~ được gọi là đẹp nếu như ~x~ chia hết cho một trong ba số sau: ~4, 7, 11~. Hãy đếm số lượng số đẹp ~x~ thỏa mãn ~L \le x \le R~.

Input

• Dòng đầu tiên chứa số ~T~ tương ứng với số lượng bộ test,
• ~T~ dòng tiếp theo, mỗi dòng chứa ~2~ số nguyên không âm tương ứng với ~L~ và ~R~.

Output

• In ra ~T~ dòng, mỗi dòng chứa một số duy nhất tương ứng với số lượng bộ đẹp

Scoring

Trong tất cả các test, ~T \le 20~

• Subtask ~1~ (~60\%~ số điểm): ~0 \le L \le R \le 10^6~.
• Subtask ~2~ (~40\%~ số điểm): ~0 \le L \le R \le 10^{12}~.

Ví dụ

Input

2
1 10
11 15

Output

3
3

Giải thích ví dụ

• Trong test ví dụ đầu tiên, có ba số thỏa mãn là ~4, 7, 8~
• Trong test ví dụ thứ hai, có ba số thỏa mãn là ~11, 12, 14~