사슴 사냥꾼

P-22는 그리피스 파크에서 사슴, 토끼 등 여러 동물을 먹이로 삼는다. 애완동물을 공격하는 일은 드물다. 다만 2016년 로스앤젤레스 동물원에서 늙은 코알라가 죽은 사건의 유력한 용의자이기도 하다. 사슴은 경계심이 매우 강하다. 살금살금 조심해서 다가가야 하고, 덮치기 전에 소리나 냄새를 들키면 안전한 곳에 닿기 전에 잡으려고 더 빨리 달려야 한다.

사냥터는 직사각형이다. 몰래 움직이는 동안 P-22는 상하좌우로 이동할 수 있지만 대각선으로는 이동할 수 없다. 입력으로 P-22와 풀을 뜯고 있는 사슴의 시작 위치가 주어진다. 두 개체 모두 자기 칸의 중앙에서 출발한다. 각 칸은 조용하거나 시끄럽다. P-22가 조용한 칸에만 머무는 동안 사슴은 그를 알아채지 못한다. 시끄러운 칸에 발을 들이면 사슴이 달리기 시작한다.

좀 더 정확히 말하면, 몰래 움직일 때 한 걸음은 P-22가 칸의 중앙에 있는 상태에서 시작해 칸의 중앙에서 끝난다. 그의 중심이 시끄러운 칸의 중앙에 놓일 때 소리가 난다. 칸의 모서리에 닿기만 해서는 소리가 나지 않는다.

사슴이 달리기 시작하면 P-22에게서 멀어지는 직선 방향으로 속력 $v_D$로 달린다. 이 직선은 지도의 격자 모양을 무시한 기하학적 직선이다. 그 순간 P-22도 속력 $v_P$로 달리기 시작해 직선을 따라 사슴을 쫓는다. 사슴이 사냥터의 가장자리에 닿기 전에 P-22가 따라잡으면 식사를 한다. 그렇지 않으면 굶는다. 사슴은 중심이 사냥터의 바깥 경계에 닿는 순간 가장자리에 도달한 것으로 본다.

달리기는 몰래 움직이는 것보다 훨씬 힘든 일이므로, P-22는 달리는 시간을 가능한 한 짧게 하고 싶다. 사슴을 잡으면서 P-22가 보장할 수 있는 달리기 구간의 최단 길이를 구하라.

첫 줄에 데이터 셋의 개수 $1 \le K \le 100$이 주어진다. 각 데이터 셋은 두 정수 $1 \le X, Y \le 1000$과 두 실수 $v_P, v_D > 0$이 적힌 줄로 시작한다. $X$는 사냥터의 너비, $Y$는 높이이며, $v_P$와 $v_D$는 각각 P-22와 사슴의 달리기 속력이다.

이어서 $Y$개의 줄이 주어지며, 각 줄은 $X$글자로 이루어진다. $y$번째 줄의 $x$번째 글자는 $y$행 $x$열 칸의 정보다.

• .은 조용한 지형이다.
• #은 시끄러운 지형이다.
• P는 P-22의 시작 칸이다.
• D는 사슴의 시작 칸이다.

두 시작 칸은 모두 조용하다. 각 데이터 셋에는 P와 D가 정확히 하나씩 들어 있다.

각 데이터 셋마다 Data Set x:를 한 줄에 출력한다. x는 데이터 셋 번호다. 다음 줄에는 사냥에 성공하는 달리기 시간의 최솟값을 소수점 둘째 자리에서 반올림해 출력한다. P-22가 사슴을 잡을 수 없으면 -1을 출력한다. P-22와 사슴은 각자 칸의 중앙에 있고, 탈출 지점은 사냥터의 바깥 가장자리임을 기억하라. 각 데이터 셋 뒤에는 빈 줄을 하나 출력한다.