PHÉP CHIA HẾT - mã: PBCDIV - SPOJ

Link: http://vn.spoj.com/problems/PBCDIV/
===========================================

Cho 2 số A và B. Tính xem có bao nhiêu số trong [A,B] chỉ chia hết cho đúng 2 trong 3 số 4, 6 và 15.

Input

-Dòng đầu là số test T (T<=10^5)

-T dòng tiếp theo mỗi dòng là 2 số nguyên A,B. (0<A<=B<=10^18)

Output

-T dòng,mỗi dòng là một kết quả của bài toán.

Example

Input:

2
1 20
2 30
Output:

1
3
================================================
Ta có: 
+ Bội chung nhỏ nhất của 4,6 là 12  ====> chia hết cho 4,6 thì chia hết cho 12
+ Bội chung nhỏ nhất của 6,15 là 30 ====> chia hết cho 6,15 thì chia hết cho 30
+ Bội chung nhỏ nhất của 4,15 là 60 ====> chia hết cho 4,15 thì chia hết cho 60

Ta có công thức sau: Số lượng số chia hết cho K trong [A,B] là: B/K - (A-1)/K...
Dễ thấy số lượng số thuộc [A,B] chia hết 2 trong 3 số 4,6,15 bằng: Số lượng số chia hết cho 12 + số lượng số chia hết cho 30 - 2 lần số lượng số chia hết cho 60.....

Chúc các bác AC ^^!