You are given an N-sided regular polygon. You have connected the center of the polygon with all the vertices, thus dividing the polygon into N equal parts.

Your task is to find the count of simple cycles that exist in the modified structure of the polygon.

Input format

• The first line contains an integer \(Q\) denoting the number of queries.
• The second line contains an integer \(N\) denoting the number of sides in the regular polygon.

Output format

Print the count of simple cycles corresponding to each query in a separate line.

Constraints
 \(1 \le N \le 10^{9}\)
\(1 \le Q \le 10^5\)