A graph which has nodes from 1 to N and there exist an edge between two nodes if Bitwise AND of those two nodes is not zero, is called AND Graph.

You are given Q queries. Each query contains N - no of nodes and two nodes A and B. For each query you have to tell minimum distance between A and B. If there doesn't exist a path between the nodes A and B, then print -1.

Input Format

• First line contains a single integer Q, the no of queries.
• Next Q lines contain three integers N (no. of nodes), node A and node B.

Output Format

• For each query, print a single line containing an integer which is equal to minimum distance between nodes, otherwise print -1.

Constraints

• 2<=N<=10¹⁸
• 1<=A,B<=N