Một hôm học toán, thầy Nqson đố các bạn TranViet, NDManh và Vu tìm các số từ 1 đến N mà chia hết cho ít nhất một trong ba số a, b, c.

Thầy HKien thấy bài dễ quá liền ra thêm yêu cầu như sau: Cho đoạn [l, r] và bốn số a, b, c, d. Hãy đếm các số x trong đoạn [l, r] sao cho:

• x chia hết cho ít nhất một trong a, b, c, và
• x không chia hết cho d.

Cả ba bạn đều chưa giải được. Bạn có thể giúp họ không?

Input

• Dòng đầu tiên chứa số nguyên T.
• T dòng tiếp theo, mỗi dòng chứa 6 số nguyên l, r, a, b, c, d.

Giới hạn:

• \( 1 \le T \le 5×10^4\)
• \( 1 ≤ l ≤ r ≤ 2×10^9 , 1 ≤ a,b,c,d ≤ 50000 \)

Output

• In ra T dòng, mỗi dòng in ra một số nguyên là kết quả tìm được.

Ví dụ

Input:

3
1 10 2 3 5 6
5 15 4 6 7 2
1 100 1 1 1 2

Output:

7
1
50

Giới hạn

Giới hạn chung:

• Thời gian: 1 giây
• Bộ nhớ: 256 MB

Giải thích ví dụ

Truy vấn 1: các số trong [1,10] chia hết cho 2, 3 hoặc 5: {2,3,4,5,6,8,9,10}. Trong đó, số chia hết cho 6 là {6} → loại. Kết quả còn {2,3,4,5,8,9,10} → 7 số.

Truy vấn 2: các số trong [5,15] chia hết cho 4, 6 hoặc 7: {6,7,8,12,14}. Những số này chia hết cho 2 (loại): {6,8,12,14}. Còn lại {7} → 1 số.

Truy vấn 3: a=b=c=1 nên mọi số đều chia hết. Yêu cầu không chia hết cho 2 → các số lẻ từ 1 đến 100 → 50 số.