All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian as well.
Mike is a famous traveler. He visits about 100 countries a year and buys the flag of each country he has been to.
Mike knows, that there are some flags, that correspond to one pattern, but colored in different ways. E.g. the flag of Ireland(link) and the flag of Belgium(link). In this problem we consider only five 2,2cm✕1,1cm patterns of flags:
There are N different colors available to paint the flags and the colors are denoted by integers from 1 to N.
Mike wants you to count the number of different well-painted flags. We call a flag well-painted if it's made according to the following algorithm:
- Pick up one of the flag patterns considered above;
- Paint each one-colored polygon on the pattern in a color encoded by an integer from 1 to N. Different colors are encoded with different integers. If two different one-colored polygons share a common side(not corner), than they must be painted in different colors. In any other case they can be painted in both equal and different colors.
Two flags are different, if they look different(have at least one pixel painted with different color).
The first line of the input contains integer T, denoting the number of testcases. The description of T testcases follows.
The only line of each test case contains integer N, denoting the number of different colors, that can be used while painting a flag pattern.
For each testcase, output a single line containing an integer - the answer for the corresponding query.
1 ≤ T ≤ 10 000;
1 ≤ N ≤ 10 000 for each testcase.
Input: 3 1 2 3 Output: 0 4 42
There are four different well-painted flags for N = 2 different colors :
Text version of the pictures:
|Tags||combinatorics, cook47, easy, kostya_by|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.