Bài toán đếm modulo

Cho hai số nguyên dương $a$ và $b$, cùng với $q$ truy vấn. Truy vấn thứ $i$ gồm hai số $l_i$ và $r_i$; đáp án của truy vấn này là số lượng số nguyên $x$ thỏa mãn:

• $l_i\le x\le r_i$, và
• $((xmoda)modb)\ne ((xmodb)moda)$.

Hãy tính đáp án cho từng truy vấn.

Nhắc lại: $ymodz$ là phần dư của phép chia $y$ cho $z$. Ví dụ, $5mod3=2$, $7mod8=7$, $9mod4=1$, $9mod9=0$.

Dữ liệu vào

Dòng đầu chứa số nguyên $t$ ($1\le t\le 100$) — số bộ test. Sau đó là $t$ bộ test.

Với mỗi bộ test:

• Dòng đầu chứa ba số nguyên $a$, $b$ và $q$ ($1\le a,b\le 200$; $1\le q\le 500$).
• Tiếp theo là $q$ dòng, mỗi dòng chứa hai số nguyên $l_i$ và $r_i$ ($1\le l_i\le r_i\le {10}^{18}$).

Dữ liệu ra

Với mỗi bộ test, in ra $q$ số nguyên trên cùng một dòng — đáp án cho các truy vấn theo đúng thứ tự xuất hiện.

Ràng buộc

• $1\le t\le 100$
• $1\le a,b\le 200$
• $1\le q\le 500$
• $1\le l_i\le r_i\le {10}^{18}$

Ví dụ