CF1342C Yet Another Counting Problem

You are given two integers $ a $ and $ b $ , and $ q $ queries. The $ i $ -th query consists of two numbers $ l_i $ and $ r_i $ , and the answer to it is the number of integers $ x $ such that $ l_i \le x \le r_i $ , and $ ((x \bmod a) \bmod b) \ne ((x \bmod b) \bmod a) $ . Calculate the answer for each query. Recall that $ y \bmod z $ is the remainder of the division of $ y $ by $ z $ . For example, $ 5 \bmod 3 = 2 $ , $ 7 \bmod 8 = 7 $ , $ 9 \bmod 4 = 1 $ , $ 9 \bmod 9 = 0 $ .

The first line contains one integer $ t $ ( $ 1 \le t \le 100 $ ) — the number of test cases. Then the test cases follow. The first line of each test case contains three integers $ a $ , $ b $ and $ q $ ( $ 1 \le a, b \le 200 $ ; $ 1 \le q \le 500 $ ). Then $ q $ lines follow, each containing two integers $ l_i $ and $ r_i $ ( $ 1 \le l_i \le r_i \le 10^{18} $ ) for the corresponding query.

For each test case, print $ q $ integers — the answers to the queries of this test case in the order they appear.