import time
import random
 
# practices 05
 
# Common input format
# -------------------
# (Read the tasks descriptions below before reading this paragraph.)
# All tasks in practices 05 set share common data input format:
# The first line contains the number of the task (1 - 5).
# The second line contains the number N of lists in the input.
# In tasks 1-4, 0 < N < 6.  In task 5, 0 < N < 12 and N is even.
# Next, there are N lines of input, each contains one input list.
# Each list consists only of integers. List entries are separated by single space,
# there are no other symbols on the input line.
# The input always contain exactly one data set of one task.
# In the evaluation system, the code is run repeatedly, each time with different input
# from which the running program reads the data.
 
# Solution code structure
# -----------------------
# The code reads the input data, including the number of the task.
# Next, it runs a function or a block of code which accepts the input data
# and computes and prints the solution to it.
# It is recommended to wrap the solution of each task in a separate function,
# an example (not obligatory!) structure of the code
# is illustrated by the contents of this file.
 
# ================================================================================
# Task 01
 
'''
In this problem, ranges are denoted in python style,
e.g. range(2, 5) spans indices 2,3,4, but not 5.
A given input array (list) consists of 3*N consecutive cells, N > 0.
Positions in range(0, N) are filled with N integers in radom order,
each of those integers is either 1 or 2.
The rest of the array is filled with 0.
The storage area for 1's is range(N, 2*N)
The storage area for 2's is range(2*N, 3*N).
 
A robot R is moving through the array, in each steps it moves from its current cell
to one of the adjacent cells.
When moving from a cell with index A to a cell with index B, the robot makes |A-B| steps.
The task of the robot is to move all values from range(0, N) to their
corresponding storage areas.
 
Robot works in cycles. In one cycle, robot
   -  moves to the rightmost cell with a non-zero value X, in range(0, N),
   -  stores 0 in that cell,
   -  moves to the leftmost cell containing 0 in the storage area for X,
   -  stores X in that cell.
 
Robot starts in cell with index 0.
Robot repeats one cycle after another, until range(0, N) contains only 0's.
 
Remark: Sroring a value X in a cells means that the original value in the cell is
overwritten by X.
 
The task
Count the number of robot steps in the whole process.
Print the result on a separate line.
The value of N does not exceed 20000.
 
Example
  Input
1
4
1 2 2 1 1 0 0 0 0 0 0 0 0 0 0
2 2 2 0 0 0 0 0 0
2 1 2 1 2 1 0 0 0 0 0 0 0 0 0 0 0 0
2 2 1 1 2 2 0 0 0 0 0 0 0 0 0 0 0 0
  Output
59
32
86
99
 
  Comment on the first list
 
After each cycle, the location of the robot (R), the contents of the array,
and the number of robot steps in that cycle is shown below.
Spaces are added for better visual clarity.
 
            R
1 2 2 1 0   1 0 0 0 0   0 0 0 0 0     5
 
              R
1 2 2 0 0   1 1 0 0 0   0 0 0 0 0     5
 
                        R
1 2 0 0 0   1 1 0 0 0   2 0 0 0 0     12
 
                          R
1 0 0 0 0   1 1 0 0 0   2 2 0 0 0     19
 
                R
0 0 0 0 0   1 1 1 0 0   2 2 0 0 0     18
'''
 
def task01( arr ):
    # your solution here
    pass
 
'''
# ------------------------------------------------------------------------------
Task02
In this problem, ranges are denoted in python style,
e.g. range(2, 5) spans indices 2,3,4, but not 5.
A given input array (list) consists of 2*N consecutive cells, N > 0.
Positions in range(0, N) are filled with N positive integers in random order,
no two values are the same.
The rest of the array is filled with 0.
 
A robot R is moving through the array, in each steps it moves from its current cell
to one of the ajacent cells.
When moving from a cell with index A to a cell with index B, the robot makes |A-B| steps.
The task of the robot is to move all values from range(0, N)
to range(N, 2*N). When the task is finished, the values in range(N, 2*N) are
sorted in ascending order and range(0, N) contains only 0's.
 
Robot works in cycles. In one cycle, robot
   -  moves to the cell which contains the smallest non-zero value X in range(0, N),
   -  stores 0 in that cell,
   -  moves to the leftmost cell containing 0 in range(N, 2*N),
   -  stores X in that cell.
 
Robot starts in cell with index 0.
Robot repeats one cycle after another, until range(0, N) contains only 0's.
 
The task
Count the number of robot steps in the whole process.
Print the result on a separate line.
The value of N does not exceed 20000.
 
Example
  Input
2
4
28 18 8 11 1 19 26 13 2 12 0 0 0 0 0 0 0 0 0 0
1 2 3 4 5 6 0 0 0 0 0 0
6 5 4 3 2 1 0 0 0 0 0 0
2 1 4 3 6 5 8 7 0 0 0 0 0 0 0 0
  Output
189
61
71
115
 
  Comment on the first list
After each cycle, the location of the robot (R), the contents of the array,
and the number of robot steps in that cycle is shown below.
Spaces are added for better visual clarity.
 
                             R
28 18 8 11 0 19 26 13 2 12   1 0 0  0  0  0  0  0  0  0     10
                               R
28 18 8 11 0 19 26 13 0 12   1 2 0  0  0  0  0  0  0  0      5
                                 R
28 18 0 11 0 19 26 13 0 12   1 2 8  0  0  0  0  0  0  0     19
                                    R
28 18 0  0 0 19 26 13 0 12   1 2 8 11  0  0  0  0  0  0     19
                                       R
28 18 0  0 0 19 26 13 0  0   1 2 8 11 12  0  0  0  0  0      9
                                          R
28 18 0  0 0 19 26  0 0  0   1 2 8 11 12 13  0  0  0  0     15
                                             R
28  0 0  0 0 19 26  0 0  0   1 2 8 11 12 13 18  0  0  0     29
                                                R
28  0 0  0 0  0 26  0 0  0   1 2 8 11 12 13 18 19  0  0     23
                                                   R
28  0 0  0 0  0  0  0 0  0   1 2 8 11 12 13 18 19 26  0     23
                                                      R
 0  0 0  0 0  0  0  0 0  0   1 2 8 11 12 13 18 19 26 28     37
'''
 
 
def task02( arr ):
    # your solution here
    pass
 
# ------------------------------------------------------------------------------
 
'''
Task 03
 
An unordered k-tuple in a list L is a multiset of k values (some values may be equal),
each of which appears at a diferent position in L. For example,
  L = [1, 2, 3, 3, 4].  Some 3-tuples in L are {1,2,3}, {1,2,4} {2,3,3}.
  Note that multisets {2,2,3}, {4,4,4}, {1,1,2} etc.  are not 3-tuples in L.
The number of all unordered k-tuples in a list L of length N
is easy to compute, it is equal to binomial coefficient(N, k) = N! // (k!*(N-k)!).
Typically, we list the items in the k-tuple in the order in which they appear in L.
 
 
The task
Find the number of such 3-tuples in a list L, each of which contains exactly two equal values.
Print the result on a separate line.
The length of L does not exceed 20000.
 
Example
  Input
  3
  4
  7 7 7 4 4 1
  8 1 7 2 6 3 5 4 8
  1 2 3 1 2 3 1 2 3
  2 2 2 2 4 4 4 4
  Output
  13
  7
  54
  48
 
  Comment
  All 20 unordered 3-tuples in the first list are listed below, by asterisk are marked
  those which contain exactly two equal values :
   1 {7,7,7}         6 {7,7,4} *      11 {7,7,4} *      16 {7,4,1}
   2 {7,7,4} *       7 {7,7,1} *      12 {7,7,4} *      17 {7,4,4} *
   3 {7,7,4} *       8 {7,4,4} *      13 {7,7,1} *      18 {7,4,1}
   4 {7,7,1} *       9 {7,4,1}        14 {7,4,4} *      19 {7,4,1}
   5 {7,7,4} *      10 {7,4,1}        15 {7,4,1}        20 {4,4,1} *
 
Hint
A most straightforward solution is to generate physically all possible 3-tuples,
select the appropriate ones, and count their number.
In Python, that can be achived by two lines of code:
   from itertools import combinations
   print( len( [x for x in combinations(L, 3) if x.count(x[0])==2 or x.count(x[1])==2] ) )
However, such approach is also less effective.
Note that the order of values in L does not matter.
It is only important how many times a particular value appears in the list.
Thus maybe there is some favourable order of values in L?
Or maybe even any particular order is unimportant, after all?
'''
 
def task03( L ):
    # your solution here
    pass
 
# ------------------------------------------------------------------------------
# Task 04
 
'''
Significance of an item I in a list A is equal to
the number of items with value I//2 located to the left of I
plus the number of items with value I*2 located to the right of I.
 
The task
Calculate the significances of all items in A.
Print item significances in the order of their corresponding items in A.
The length of A does not exceed 40000.
 
 
Example
  Input
4
5
5 5 5 10 20 20
10 20 30 40 50 60 70 80
1 1 2 2 4 4 8 8 16 16 32 32
1 2 1 3 2 6 3 2 4 6
11 22 11 22 44 88 44 88 44
  Output
1 1 1 5 1 1
1 2 1 2 0 1 0 1
2 2 4 4 4 4 4 4 4 4 2 2
3 2 2 4 3 1 3 3 3 2
2 4 1 5 4 1 3 2 2
 
Hint:
  In python, with the help of list comprehension, all significances can be
  computed on one line, e.g by statement
     signif = [ A[:i].count(A[i]//2) + A[i:].count(A[i]*2) for i in range(len(A)) ].
  However, for each separate value i, the statement scans and checks all items
  in the entire list A. Thus, to finish the task, the program has to inspect
  N times the entire list of N items, when the length of the list is N.
  That is N*N item inspections in total.
 
  An alternative way of solution may depend on binary search.
  Imagine, that there is an additional list B of all values which appear in A.
  Each value X in B is associated with a sorted list of *all positions*
  at which X appears in A.
  Now, when calculating a significance of an item A[i] at position i,
  first find A[i]//2 in B with the help of binary search,
  and then count all positions of A[i]//2 to the left of i.
  This last counting can be again done effectively with the help
  of the list of positions associated with A[i]//2 in B, and another binary search in it.
 
  Also, instead of list B, you may try to employ a dictionary B of positions of item values.
'''
 
def task04( A ):
    # your solution here
    pass
 
 
# ------------------------------------------------------------------------------
'''
Task 05
 
 
An informal description of the problem, by a purpotedly "real life" situation,
may help to grasp quickly the abstract core of the problem.
Nonetheless, it does not quarantee better understanding
or better choice of an appropriate solution method.
But still, if presented correctly, it simplifies formulation of one's own ideas,
and that speeds up the entire solution process..., sometimes. :-)
 
There is a group A of sport trainers and a group B of students.
Each person in both groups is an owner of some number of dogs fit for a sledge race.
A racing team consists of one trainer and two students, each person in the team
has to bring all their dogs to the race.
However, the number of dogs in one team is strictly prescribed,
it has to be exactly  S dogs (S > 0).
Therefore, when a trainer wants to choose a pair of students who
will join him to make a team, he cannot choose an arbitrary pair of students.
The number of dogs owned by the trainer plus the sum of  number of dogs
owned by both his prospective teammates has to be exactly S.
The number of owned dogs varies from person to person,
among the trainers and among the students as well.
Thus, for a trainer, there is only a limited number of pairs among 
the studens whom he can ask to join him in a team.
This limitation leads to the definition of capacity.
The capacity of a trainer is the number of different pairs of students
who can form a team with the trainer.
  The task
Sort the trainers in increasing order of their capacities.
When the capacities of some trainers are equal, those trainers are sorted in
ascending order of the number of dogs they own.
You may assume that each person owns less than 100 dogs.
 
 
Abstract formulation
 
A pair in a list L is a 2-tuple in L ( see k-tuple definition in task 3 )
Let A and B be two lists of integers.
For each item I in A, the capacity of I is equal to the number such of pairs {a, b} in B
for which it holds  Sum(a, b) + I = S.
 
The task
Sort items in A in ascending order of their capacities.
When the capacities of some items are equal, those items are sorted in
ascending order of their values.
Print the sorted items on one line, in the same format as input.
The value of S happens to be the sum of the first three items in B.
All items in A and B are positive and less than 100.
The lengths of A and B do not exceed 20000.
 
 
Example
  Input
5
8
2 4 6 8 10 12
5 6 7 1 2 3 4 5 6 7 8 9 10 11 12
11 12 32 31 22 21
10 10 10 5 10 15 20 25
11 12 32 31 22 21
10 10 10 4 5 9 10 14 20 24
5 10 15
15 10 5 20 20 20 5 5 5
 
  Output
12 10 2 8 4 6
11 12 21 22 31 32
22 31 32 12 21 11
10 15 5
'''
 
 
def task05( A, B ):
    # your solution here
    pass
 
 
# * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
#               I N P U T    R E A D I N G
taskNo = int(input())
Nlists = int(input())
inputLists = []
for k in range(Nlists):
    oneList = list(map(int, input().split()))
    inputLists.append(oneList)
 
# * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
#             P R O C E S S I N G
 
t1 = time.time()
if taskNo in [1, 2, 3, 4]:
    for aList in inputLists:
        if taskNo == 1:  task01(aList)
        if taskNo == 2:  task02(aList)
        if taskNo == 3:  task03(aList)
        if taskNo == 4:  task04(aList)
if taskNo in [5]:
    for i in range(0, len(inputLists), 2):       # pairs of lists
        task05(inputLists[i], inputLists[i + 1])
 
t2 = time.time()
# print( 'time', str(t2-t1)[:5] )