We have n cities labeled from 1 to n . Two different cities with labels x and y are directly connected by a bidirectional road if and only if x and y share a common divisor strictly greater than some threshold . More formally, cities with labels x and y have a road between them if there exists an integer z such that all of the following are true:
x % z == 0 ,
y % z == 0 , and
z > threshold .
Given the two integers, n and threshold , and an array of queries , you must determine for each queries[i] = [a _i , b _i ] if cities a _i and b _i are connected directly or indirectly. (i.e. there is some path between them).
Return an array answer , where answer.length == queries.length and answer[i] is true if for the i ^th query, there is a path between a _i and b _i , or answer[i] is false if there is no path.
2 <= n <= 10 ^40 <= threshold <= n1 <= queries.length <= 10 ^5queries[i].length == 21 <= a _i , b _i <= citiesa _i != b _i