# Problem F

Fractal Area

*Circle-Square Fractal*, or

*CS Fractal*(which also goes by other names), is a simple two-dimensional fractal constructed in an iterative fashion out of solid circles of decreasing radii. As the construction proceeds, certain square regions become noticeable (in particular, the entire fractal), hence the “Square” part of the name.

The $1^{\mathrm{st}}$
iteration in the construction of the CS Fractal consists
of a single circle of radius $r
> 0$. In the $2^{\mathrm{nd}}$ iteration, this
“parent” circle spawns four “child” circles of radius
$r/2$ that are tangent to
the parent circle in each of the north, south, east, and west
directions. Now let $n \geq 3$.
In the $n^{\mathrm{th}}$
iteration, each circle $C$ added in the $(n-1)^{\mathrm{st}}$ iteration spawns
*three* child circles whose radii are exactly half of
$C$’s radius, and that are
tangent to $C$ in each of
the three compass directions *other than the direction in
which $C$ touches its
parent circle* (here the compass directions are relatively
to $C$). For example,
in the $3^{\mathrm{rd}}$
iteration, the circle $C$
of radius $r/2$ that is
north of the $1^\mathrm {st}$-generation
circle spawns three circles of radius $r/4$ that touch $C$ in its west, north, and east
directions. The illustration accompanying this problem depicts
the CS Fractal after $6$ iterations. (Technically, the
fractal is the shape generated after infinitely many
iterations, but we informally use “fractal” to refer to the
partially constructed shape after a finite number of
iterations.)

Given the radius of the starting ($1^{\mathrm{st}}$-iteration) circle and the number of iterations, determine the area of the partially constructed fractal.

*Note:* Other than the single-point intersection
between any child circle and its parent, no two circles in the
fractal intersect.

## Input

The first line of input contains an integer $T$, the number of test cases ($1 \leq T \leq 50$). This is followed by $T$ lines, one per test case, each of which contains two space-separated integers, $r$ and $n$ ($1 \leq r \leq 200$, $1 \leq n \leq 50$), where $r$ is the radius of the starting ($1^{\mathrm{st}}$-iteration) circle and $n$ is the number of iterations.

## Output

For each test case, output the area of the partially constructed fractal with starting radius $r$ after $n$ iterations. Each computed area will be considered correct if it is within $10^{-6}$ of the official answer.

Sample Input 1 | Sample Output 1 |
---|---|

2 1 1 8 3 |
3.141592653589793 552.9203070318035 |