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~ và ~11~. Hãy đếm số lượng số đẹp ~x~ thỏa mãn ~L ≤ x ≤ 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~.

Giới hạn:Trong tất cả các test, ~T ≤ 20~.

• Subtask #1 ~(60\%): 0 ≤ L ≤ R ≤ 10^6~;
• Subtask #2 ~(40\%): 0 ≤ L ≤ R ≤ 10^{12}~.

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 số đẹp.

Sample

Input #1

2
1 10
11 15

Output #1

3
3

Hint

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

Problem source: Kc97ble - Free Contest