표준API 메뉴얼: C++, C언어, Java,  Python,  Python3,  Kotlin,  C#, Go, Swift, Javascript, Ruby, Scala

 철수는 모바일 게임 점프! 점프!를 플레이하고 있다. 이 게임은 지도상에 존재하는 여러 지점을 정복하고 또 방어해야하는 게임이다. 하지만 자신이 점유하고 있는 지점이 많아질 수록 수비하기가 어려워지는 문제점이 있다. 그래서 이 게임에서 유저는 자신만의 순간이동 장치를 가지고 있다. 자신의 캐릭터가 성장할 수록 순간이동 장치의 성능이 올라가게 되므로 더 많은 영역을 정복하고 방어할 수 있게 된다. 

그림 1. 점 A(7, 6)에서 성능이 R=16인 순간 이동기를 한 번사용했을 때 이동가능한 범위의 예시. 점 B, E등은 거리가 이하이기 때문에 이동할 수 있다. 점 F, D등은 거리가 보다 멀기 때문에 이동할 수 없다. X/Y좌표가 모두 정수인 점으로만 이동할 수 있음에 유의하라.

 현재 철수의 순간이동 장치는 R의 성능을 가지고 있다. 이 말은 현재 철수의 캐릭터가 위치한 지점에서 2차원 좌표상으로 거리가 이하인 지점으로 한 번에 순간이동 할 수 있는 성능이다. 단, 모든 지점은 X/Y좌표가 정수인 점위에만 존재한다. 순간이동장치를 사용할 수 있는 규칙은 위의 그림 1을 참고하자.

그림2. 원점 P0(0, 0)에서 성능이 R=1인 순간이동이를 최대 K=2번 사용해 도달할 수 있는 13개의 점을 나타내는 그림.

 가장 처음 게임을 시작하면 원점 P0(0,0)위에 있는 지점을 본진으로 점유한 상태다. 즉, 최소 하나의 지점은 항상 점유하고 있다. 본진은 다른 플레이어에게 침략받지 않는다고 가정한다.

 철수는 안전한 플레이를 위해 너무 멀지 않는 지점들만을 점령하여 수비를 용이하게 하려고 한다. 원점상에 존재하는 본진으로부터 순간이동 장치를 사용해 K번 이내에 도달할 수 있는 영역들만을 침략하여 점유하려고 할 때, 철수가 동시에 점유할 수 있는 이론상 최대의 지점 수는 몇 개인가? 철수의 승리를 위해 이를 계산해주는 프로그램을 작성하시오.

입력 형식

 첫 줄에는 테스트케이스의 수를 나타내는 1이상 100이하의 자연수 T가 주어진다. 이후 총 T개의 테스트케이스에 대한 입력이 차례로 주어진다. 

 각 테스트케이스에 대한 입력은 공백으로 구분된 두 개의 정수가 R K 형식으로 한 줄에 주어진다.

• R은 순간이동장치의 성능을 나타내는 1이상 10억이하의 자연수다.
• K는 지점 방어를 위해 최대로 순간이동장치를 사용할 횟수를 나타내는 0이상 1만이하의 정수다.

출력 형식

 각 테스트케이스에 대한 정답을 한 줄씩 차례로 출력한다.

• 성능이 R인 순간이동 장치를 최대 K번 사용해 방어할 수 있는 지점의 수를 출력한다.