Cho \(7\) số tự nhiên \(A, B, C, D, E, F, G\).
Yêu cầu: Hãy tìm số lượng số nguyên \(x \in [A, B] \text{ }(\text{tức }A \le x \le B)\) thỏa mãn đồng thời các điều kiện sau:

1. \(x\) chia hết cho ít nhất một trong ba số \(C, D, E\).
2. \(x\) không chia hết cho \(F\).
3. \(x\) không chia hết cho \(G\).

Input

• Dòng đầu tiên chứa số nguyên \(T\) (\(1 \le T \le 1000\)) — số lượng bộ test.
• Mỗi dòng trong số \(T\) dòng tiếp theo chứa bảy số tự nhiên \(A, B, C, D, E, F, G\) (\(1 \le A \le B \le 10^{18}\), \(1 \le C, D, E, F, G \le 10^9\)).

Output

• Với mỗi bộ test, in ra trên một dòng một số nguyên duy nhất là số lượng số \(x\) thỏa mãn yêu cầu.

Example

2
1 20 2 3 5 4 6
10 100 3 5 7 2 11

8
23