n towns numbered 1 to n. Towns x and y have a direct road between them when their numbers share a common divisor strictly greater than limit. Roads go both ways.
For every query [a, b] in queries, decide whether town b can be reached from town a, either directly or through other towns.
Return a list of True and False values, one per query, in the same order.n=8, limit=2, queries=[[3, 6], [4, 8], [2, 3], [5, 7]] → [True, True, False, False]
3 and 6 share 3, and 4 and 8 share 4, so both pairs have a direct road. Town 2 has no divisor above 2, and 5 and 7 have no other multiples up to 8, so they are cut off.
n=12, limit=1, queries=[[3, 4], [5, 7]] → [True, False]
3 → 6 (share 3) → 4 (share 2) gives a path. 7 could only link to 14, which does not exist, so 5 and 7 are not connected.
n=4, limit=0, queries=[[1, 4], [2, 3]] → [True, True]
With limit 0 the divisor 1 qualifies, and every number is divisible by it, so all towns are connected.
n=8, limit=2, queries=[[3, 6], [4, 8], [2, 3], [5, 7]]
[True, True, False, False]
Run checks the first 3 tests in your browser. Submit checks all 66 tests on the server, hidden ones included.