Đếm Nghiệm Trong Giới Hạn · canuc80k5404

Mỗi bộ dữ liệu cho một giới hạn trên $N$ và $M$ điều kiện về số dư. Một số nguyên dương $X$ hợp lệ khi $X mod a_{i} = b_{i}$ với mọi $i$ .

Hãy đếm bao nhiêu giá trị $X$ trong đoạn từ $1$ đến $N$ là hợp lệ.

Input

Dòng đầu chứa $T$ . Mỗi bộ dữ liệu gồm dòng $N$ $M$ , một dòng chứa $M$ số $a_{i}$ , rồi một dòng chứa $M$ số $b_{i}$ .

Output

Với mỗi bộ dữ liệu, in số lượng giá trị $X$ hợp lệ.

Constraints

$1 \leq T \leq 100$ .
$1 \leq N \leq 1 0^{9}$ ; $1 \leq M \leq 10$ .
$1 \leq a_{i} \leq 10$ ; $0 \leq b_{i} < a_{i}$ .

Scoring

Subtask $1$ ( $50%$ số điểm): $T \leq 4, N \leq 120, M \leq 5$ và $a_{i} \leq 5$ .
Subtask $2$ ( $50%$ số điểm): không có giới hạn bổ sung.

Example

Test 1

Input

Output

1
5

Giải thích: Trong đoạn $1, \dots, 20$ , chỉ có $10$ thỏa hai số dư của bộ đầu. Với bộ sau, các bội dương của $6$ không vượt $30$ là $6, 12, 18, 24, 30$ , nên có năm giá trị.

Mô hình: Với mỗi bộ dữ liệu, ta có một cận N và M điều kiện về số dư. Một số nguyên dương X hợp lệ khi X mod a_i = b_i với mọi i.
Mô hình: Nhiệm vụ là đếm bao nhiêu giá trị X trong đoạn từ 1 đến N là hợp lệ.
Thuật toán: Ghép toàn bộ hệ thành một trong hai kết quả:
Thuật toán: vô nghiệm: đáp án 0;
Thuật toán: x ≡ r (mod L), 0 <= r < L.
Thuật toán: Nếu r=0, các nghiệm dương là L,2L,3L,... nên có floor(N/L) nghiệm. Nếu r>0 và r<=N, các nghiệm là r,r+L,..., do đó số lượng là
Thuật toán: floor((N-r)/L)+1.
Thuật toán: Nếu r>N thì đáp án 0.
Chứng minh đúng đắn: EXCRT bảo đảm lớp r modulo L chứa đúng và đủ các nghiệm của hệ. Các phần tử trong lớp tăng đều L đơn vị, nên công thức đếm cấp số cộng là chính xác. Việc tách r=0 loại riêng số 0, vốn không thuộc tập số nguyên dương mà đề yêu cầu.
Độ phức tạp: O(M log max a_i) mỗi test; O(M) bộ nhớ.
Lỗi thường gặp: Dùng (N-r)/L+1 khi r=0 và vô tình đếm X=0.
Lỗi thường gặp: Không kiểm tra r>N.
Lỗi thường gặp: Cho rằng vì a_i <= 10 nên cứ vét X đến N; N có thể tới 10^9.