Ada King Solution

 

Problem

Chef Ada is training to defend her title of World Chess Champion.

To train her calculation skills, Ada placed a king on a chessboard. Remember that a chessboard has $8$ rows and $8$ columns (for the purposes of this problem, both the rows and the columns are numbered $1$ through $8$); let's denote the square in row $r$ and column $c$ by $(r, c)$. A king on a square $(r, c)$ can move to another square $(r', c')$ if and only if $(r'-r)^2+(c'-c)^2 \le 2$.

Ada placed her king on the square $(R, C)$. Now, she is counting the number of squares that can be visited (reached) by the king in at most $K$ moves. Help Ada verify her answers.

Input

• The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
• The first and only line of each test case contains three space-separated integers $R$, $C$ and $K$.

Output

For each test case, print a single line containing one integer — the number of squares the king can visit.

Constraints

• $1 \le T \le 512$
• $1 \le R, C, K \le 8$

Sample 1:

Input

Output

1
1 3 1

6

Explanation:

Example case 1: The king can stay on its original square or move to one of the squares circled in the following figure.

Program :

#include <stdio.h>

int main(void) {

// your code goes here

int t;

scanf("%d",&t);

while(t--)

{

    int p,q,k,ans=0,i,j;

    scanf("%d %d %d",&p,&q,&k);

    for(i=1;i<=8;i++)

        {

             for(j=1;j<=8;j++)

             {

                 if(pow((i-p),2)<=pow(k,2)&&pow((j-q),2)<=pow(k,2))

                 {

                     ans++;

                 }

             }

        }

   printf("%d\n",ans);

}

return 0;

}