Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Arrange the Bricks!

By Shahwat_Has9 · Limits 1s, 512 MB

You have NN bricks two dimensional bricks of the dimension 1×21 \times 2. The bricks are rotatable i.e. you can turn the brick of dimension 1×21 \times 2 into 2×12 \times 1. Now, you have to determine how many different rectangular shapes can you create by arranging the bricks. Two rectangular shapes are different if their dimensions are different. There should be no space left in the rectangular shapes that you create with the bricks i.e they must be filled with bricks.

Note: Dimension a×ba \times b and b×ab \times a considered same.

Input

In the first line, there will be an integer TT, the number of testcases.

In the next TT lines, there will be an integer NN, indicating the number of bricks you will receive.

For Subtask 1: (30 points)

  • 1T10001 \le T \le 1000
  • 1N100001 \le N \le 10000

For Subtask 2: (30 points)

  • 1T1001 \le T \le 100
  • 1N10121 \le N \le 10^{12}

For Subtask 3: (40points)

  • 1T1001 \le T \le 100
  • 1N10141 \le N \le 10^{14}

Output

For each NN, print the number of ways you can arrange the bricks.

Sample

InputOutput
4
1
2 
3 
4
1
2
2
2

Possible Dimension for 1 bricks are: 1 x 2

Possible Dimension for 2 bricks are: 2 x 2, 4 x 1

Possible Dimension for 3 bricks are: 1 x 6, 2 x 3

Possible DImension for 4 bricks are: 4 x 2, 1 x 8


Discussion

Statistics


38% Solution Ratio

Samin_SieyamEarliest, Jun '20

YouKnowWhoFastest, 0.0s

CCS_RUSHIKONLightest, 131 kB

JarifDotTechShortest, 434B

Submit

Login to submit

Editorial

This problem is a representation of NOD problem. Here, NOD = Number of Divisor. NOD Counting with pr...

Toph uses cookies. By continuing you agree to our Cookie Policy.