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$