1. Crazy cubes
There is a store room which has only three sides all touching each other perpendicularly, the sides can be
defined as: two infinitely large walls and one infinitely large floor.
There are N cubes of unit volume. You need to store the cubes in the store room but there are 2 rules to be
followed before storing:

1. A cube can be placed anywhere on the floor.
2. If a cube A is placed upon another cube B, then there should be a cube on all the four sides of the cube B
   unless the side is already blocked by a wall.
   You need to output the minimum floor area covered for storing N cubes.
   Example
3. N = 3 requires 3 unit square of floor area as all the cubes need to be placed on the floor.
4. N = 4 requires 3 unit square of floor area. Let there be cubes A, B, C, D; cube A can be placed above the
   cube B, which is touching both the walls. Since cube B is touching both the walls it is blocked on 2 sides but
   open on 2 other sides, cubes C and D can be placed on the adjacent open sides of Cube B. Hence, Cube A
   can be placed on the cube B following the given rules.
   Constraints:

• T (number of test cases) <= 10
  6
• N (number of cubes for each test case) <=10
  18

Input:
First-line contains an integer T, the number of test cases.
Each of the next T lines contains an integer N, the number of cubes.
Output:
For each test case, print the correct output in a new line.

Sample Input 0 :
2
3
4
Sample Output 0 :
3
3

2. War with China
India has decided to rage a war against China, and has decided they want to destroy them in D days.
China consists of N cities each having powerful defense systems which will try to avoid the attack as
much as possible.
India has developed a secret missile which just need to be fired once and can cause chaining damage.
The missile is launched with attack score of Y on DAY 0. All the cities having defense score less than or
equal to Y will be demolished instantly.
On the ith day for i>0 , all the cities which are at a exact distance of i from cities which were demolished
on DAY 0 will loose Y from their defense score and will get demolished if their defense score decreases
below 1.
As building such a powerful weapon costs a lot, so India wants to minimize their cost by finding the least
possible attack score for their missile such that all the cities are demolished before D days.
INPUT
First line of input contains two space separated integer N and D, denoting number of cities and number of
days in which India must destroy all the cities in China.
Next line of input contains N integers where each integer denotes defense score of each city.
OUTPUT
You have to output minimum attack score of the missile that India must use in order to succeed.
CONSTRAINTS
1 <= N <= 10^6
1 <= Ai <= 10^9
1 <= D <= 10^5

SAMPLE INPUT
3 1
5 10 5
SAMPLE OUTPUT
5

EXPLAINATION
Clearly, India cannot make a missile with attack score less than 5, because no cities will be affected.
If India choses 5, then on Day 0 City 1 and City 3 will be demolished.
City 1:
On Day 1, It will decrease the defense of city 2 by 5. On Day 2, It will decrease the power of city 3 by 5.
(Note that this city is already destroyed)
City 3 :
On Day 1, It will decrease the defense of city 2 by 5. On Day 2, It will decrease the power of city 3 by 5.
(Note that this city is already destroyed)
We can see clearly that for City 2 on Day 1, The power decreases by (10 = 5 + 5). Hence, it gets
destroyed.

3. Metrics
A new app was developed and launched in the market and you were hired as an engineer to
monitor its performance.
This app generates two types of metrics for monitoring purposes. The count of the number of
requests received by the app and the latency/duration of the request. Whenever a new request
arrives, the app either publishes the count or the latency data point along with the timestamp. Let
us denote the count metric by Cand latency metric by L.
Now, these metrics are generated in large numbers and some aggregation should be performed to
minimize the number of data points and save some memory in the database. Now you have a
monitoring tool that collects data points that are published in an interval of T seconds and
performs aggregations. For example, If the monitoring tool collected 5 different data points in a
single interval:
C C L C L
It’ll be aggregated as (3C, 2L). Now we only need to store 2 data points instead of 5.
Now here is the caveat, it’s useful to aggregate multiple count data points since the values are not
unique but it’s not useful to aggregate many Latency data points since every latency point is unique,
and taking a sum/average can lead to loss of useful insights. So it’s valuable to have as many
latency data points as possible.
Let us denote the Business cost to store 1 count data point as BC and the Business value to have
1 latency data point as BV.
You’re given N data points with a timestamp, You need to print the minimum time interval T that
you need to set in your monitoring tool such that the Business Profit (Total Business Value - Total
Business Cost) is maximum.
Input:

• First-line consists of the total number of data points N
• Next N lines consist of a data point with timestamp TS
• The last line consists of 2 values, Business cost of a single count (BC) and Business value of
  single latency metric (BV)
  Output:
  Print the minimum value T (Time interval) of monitoring tool, such that (Total BV - Total BC) is
  maximum
  Constraints:
  1 <= N <= 10^5
  1 <= TS <= 10^4
  1 <= BC, BV <= 10^9

Sample Input
5
C 1
L 3
C 4
C 8
L 10
2 3
Sample Output
8
Explanation
If the timer interval is set to 8 then the aggregation would produce 3 data points [(3C, L), (L)]
which produces the Business profit of 4 (2*3 - 1*2).
Sample Input
5
C 1
L 3
C 4
L 8
C 10
3 2
Sample Output
10

Explanation
If the timer interval is set to 10 then the aggregation would produce 2 data points [(3C, 2L)] which
produces the Business profit of -1 (1*2 - 1*3).