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 denoting the number of queries. The second line contains an integer 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.