In his childhood Ashiqul Islam was very romantic. One day he saw his childhood crush standing on the boundary of a circular road, Ashiqul was also on that road but in a different position. There was a rose strictly outside the circle. As a romantic kiddo, Ashiqul wanted to bring the rose to his crush. Interestingly, his crush likes geometry problems. So, After ashiqul gave if rose to her and said "I love you." His crush replied, "I only love people who loves geometry. Now, If you can solve this geometry problem, I will love you." The position of the rose, Ashiqul and his crush is P , Q and R respectively. R is always on the intersection of the circle and the line PQ. You are given the center O(x1, y1) and radius r of the circle and the position P(x2, y2) of the rose. You have the calculate the minimum possible value of PQ.PR for all possible position Q. Unfortunately Ashiqul is very lazy and given this problem to you.

Input

First line of input contains number of test cases T (1<= T <= 1000). Each of the next T lines will contain 5 integers x1, y1, r, x2, y2 respectively in a line. -100000<= x1, y1, x2, y2 <= 100000 and 1 <= r <= 100000.

Output

For each line of input, output will contain only one integer, minimal possible value of PQ.PR