Statement

Azugand, the city from the famous Prahovand Valley, is known for its peculiar structure: it has N intersections, numbered from 1 to N, all of which has an assigned value V_i. Two distinct intersections have a street between them if and only if the bitwise AND (represented as &) of their values is non-zero. Formally, you are given a graph with N vertices, each vertex having a value V_i assigned to it. We have an edge between two distinct vertices i and j iff V_i & V_j ≠ 0. Andrei, a well-known child from the valley, wants to make a table with the shortest distances between two points of interest, but he is overwhelmed by the number of queries he wants to solve, so he asks for your help! You are given Q queries, in which you have to compute cost(X, Y). We define cost(X, Y) as the minimum number of edges that are in the shortest path in the graph between vertices X and Y. If we can't reach vertex Y from vertex X, then the value of cost(X, Y) is -1.