Given ~n~ testcases in the form of ~a,b~. For each testcase, print ~a+b~.

Input

The first line contains the number ~n~. The next ~n~ lines contain the numbers ~a,b~, separated by a space character.

Output

The answer of the problem.

Sample Input

3
9 8
17 35
732 901

Sample Output

17
52
1633

Limits

~n\le50~

~a,b\le10^{12}~

Given ~n~ testcases in the form of ~a,b~. For each testcase, print ~a-b~.

Input

The first line contains the number ~n~. The next ~n~ lines contain the numbers ~a,b~, separated by a space character.

Output

The answer of the problem.

Sample Input

3
9 8
67 35
1732 901

Sample Output

1
32
831

Limits

~n\le50~

~a,b\le10^{12}~

Given ~n~ testcases in the form of ~a,b~. For each testcase, print ~ab~.

Input

The first line contains the number ~n~. The next ~n~ lines contain the numbers ~a,b~, separated by a space character.

Output

The answer of the problem.

Sample Input

3
9 8
67 35
1732 901

Sample Output

72
2345
1560532

Limits

~n\le50~

~a,b\le10^{12}~

Given ~n~ testcases in the form of ~a,b~. For each testcase, print ~\big\lfloor \frac{a}{b} \big\rfloor~.

Input

The first line contains the number ~n~. The next ~n~ lines contain the numbers ~a,b~, separated by a space character.

Output

The answer of the problem.

Sample Input

3
9 8
97 35
5932 901

Sample Output

1
2
6

Limits

~n\le50~

~a,b\le10^{12}~

Given ~n~ testcases in the form of ~a,k~. For each testcase, print ~a~ rounded to the ~k~th decimal digit.

Input

The first line contains the number ~n~. The next ~n~ lines contain the numbers ~a,k~, separated by a space character.

Output

The answer of the problem.

Sample Input

3
7.7567 2
937.6874 6
7392.3644724 3

Sample Output

7.76
937.687400
7392.364

Limits

~n\le50~

~a\le10^{12}, k\le15~.

Ensure that the precision of ~a~ does not exceed ~12~ digits.

Given ~n~ testcases in the form of ~a~. For each testcase, print the ceiling, floor, and the nearest integer of ~a~.

Input

The first line contains the number ~n~. The next ~n~ lines contain the number ~a~, separated by a space character.

Output

The answer of the problem.

Sample Input

3
7.7567
937.6874
7392.3644724

Sample Output

8 7 8
938 937 938
7393 7392 7392

Limits

~n\le50~

~a\le10^{12}~.

Ensure that the precision of ~a~ does not exceed ~20~ digits.

Given ~n~ testcases in the form of ~a,k~. For each testcase, print ~\big\lfloor\sqrt[k]{a}\big\rfloor~.

Input

The first line contains the number ~n~. The next ~n~ lines contain the numbers ~a,k~, separated by a space character.

Output

The answer of the problem.

Sample Input

3
7243555435325 2
45582323455342543523345434 8
32493454554355543452354324353243413241242334323943 20

Sample Output

2691385
1611
298

Limits

~n\le50~

~a\le10^{50},k\le50~.

Given ~n~ testcases in the form of ~a,k~. For each testcase, print ~\log_k a~.

Input

The first line contains the number ~n~. The next ~n~ lines contain the numbers ~a,k~, separated by a space character.

Output

The answer of the problem.

Sample Input

3
7243555435325 2
45582323455342543523345434 8
32493454554355543452354324353243413241242334323943 20

Sample Output

42
28
38

Limits

~n\le50~

~a\le10^{50},2\le k\le50~.

Given ~n~ testcases in the form of ~a,k~. For each testcase, print ~a\mod k~.

Input

The first line contains the number ~n~. The next ~n~ lines contain the numbers ~a,k~, separated by a space character.

Output

The answer of the problem.

Sample Input

3
39 2
34788 63
464823643 35324

Sample Output

1
12
30451

Limits

~n\le50~

~a\le10^{50},k\le10^{20}~.

Given ~n~ testcases in the form of ~a,k~. For each testcase, print ~a^k\mod(10^9+7)~.

Input

The first line contains the number ~n~. The next ~n~ lines contain the numbers ~a,k~, separated by a space character.

Output

The answer of the problem.

Sample Input

3
8 2
78 23
9837 82

Sample Output

64
997321536
872492220

Limits

~n\le50~

~a\le10^{20},k\le10^{4}~.

A rectangle has length ~a~ and width ~b~. Calculate its perimeter and area.

Input

The first line contains the number ~n~. The next ~n~ lines contain the numbers ~a,b~, separated by a space character.

Output

The answer of the problem.

Sample Input

3
8 2
78 23
9837 82

Sample Output

20 16
202 1794
19838 806634

Limits

~n\le50~

~a\le10^{50},k\le10^{50}~.

A triangle has base ~a~ and height ~b~. Calculate its area rounded to ~1~ digit of precision.

Input

The first line contains the number ~n~. The next ~n~ lines contain the numbers ~a,b~, separated by a space character.

Output

The answer of the problem.

Sample Input

3
8 2
78 23
9837 82

Sample Output

8.0
897.0
403317.0

Limits

~n\le50~

~a\le10^{10},k\le10^{10}~.

A rhombus has diagonals of length ~a~ and ~b~. Calculate its area rounded to ~1~ digit of precision.

Input

The first line contains the number ~n~. The next ~n~ lines contain the numbers ~a,b~, separated by a space character.

Output

The answer of the problem.

Sample Input

3
8 2
78 23
9837 82

Sample Output

8.0
897.0
403317.0

Limits

~n\le50~

~a\le10^{20},k\le10^{20}~.

A trapezoid has bases of length ~a~ and ~b~ and height ~h~. Calculate its area rounded to ~1~ digit of precision.

Input

The first line contains the number ~n~. The next ~n~ lines contain the numbers ~a,b,h~, separated by a space character.

Output

The answer of the problem.

Sample Input

3
8 2 8
78 23 46
9837 82 55

Sample Output

40.0
2323.0
272772.5

Limits

~n\le50~

~a,b,k\le10^{10}~.

A circle has radius ~r~. Calculate its perimeter and area rounded to ~2~ digits of precision. Assume ~\pi=3.14~.

Input

The first line contains the number ~n~. The next ~n~ lines contain the number ~r~, separated by a space character.

Output

The answer of the problem.

Sample Input

3
8
78
9837

Sample Output

50.24 200.96
489.84 19103.76
61776.36 303847026.66

Limits

~n\le50~

~r\le10^{10}~.

A right triangle has legs of length ~a~ and ~b~. Calculate the hypotenuse rounded to ~2~ digits of precision.

Input

The first line contains the number ~n~. The next ~n~ lines contain the number ~a,b~, separated by a space character.

Output

The answer of the problem.

Sample Input

3
3 4
5 12
9 12

Sample Output

5.00
13.00
16.00

Limits

~n\le50~

~a,b\le10^{10}~.

A triangle has side lengths ~a,b,c~. If it is a valid triangle, print YES, else print NO.

Input

The first line contains the number ~n~. The next ~n~ lines contain the numbers ~a,b,c~, separated by a space character.

Output

The answer of the problem.

Sample Input

3
3 4 5
7 7 7
9 1 11

Sample Output

YES
YES
NO

Limits

~n\le50~

~a,b,c\le10^{10}~.

A triangle has angles ~a,b,c~. If it is a valid triangle, print YES, else print NO.

Input

The first line contains the number ~n~. The next ~n~ lines contain the numbers ~a,b,c~, separated by a space character.

Output

The answer of the problem.

Sample Input

3
90 90 1
77 67 57
60 60 60

Sample Output

NO
NO
YES

Limits

~n\le50~

~a,b,c\le180~.

A triangle has side lengths ~a,b,c~. If it is a valid triangle, print its area rounded to ~2~ decimal digits, else print NO.

Input

The first line contains the number ~n~. The next ~n~ lines contain the numbers ~a,b,c~, separated by a space character.

Output

The answer of the problem.

Sample Input

3
3 4 5
5 12 13
1 2 3

Sample Output

6.00
30.00
NO

Limits

~n\le50~

~a,b,c\le10^{10}~.

A triangle has side lengths ~a,b,c~. If it is a valid triangle, print its inscribing circle radius rounded to ~2~ decimal digits, else print NO.

Input

The first line contains the number ~n~. The next ~n~ lines contain the numbers ~a,b,c~, separated by a space character.

Output

The answer of the problem.

Sample Input

3
3 4 5
5 12 13
1 2 3

Sample Output

1.00
2.00
NO

Limits

~n\le50~

~a,b,c\le10^{10}~.

A triangle has side lengths ~a,b,c~. If it is a valid triangle, print its circumcircle radius rounded to ~2~ decimal digits, else print NO.

Input

The first line contains the number ~n~. The next ~n~ lines contain the numbers ~a,b,c~, separated by a space character.

Output

The answer of the problem.

Sample Input

2
3 4 5
1 2 3

Sample Output

2.50
NO

Limits

~n\le50~

~a,b,c\le10^{10}~.

A triangle has side lengths ~a,b,c~. If it is a valid triangle, print its type, else print INVALID. The type of the triangle can be SCALENE, ISOSCELES, or REGULAR.

Input

The first line contains the number ~n~. The next ~n~ lines contain the numbers ~a,b,c~, separated by a space character.

Output

The answer of the problem.

Sample Input

4
7 7 7
7 7 6
7 6 5
7 1 1

Sample Output

REGULAR
ISOSCELES
SCALENE
INVALID

Limits

~n\le50~

~a,b,c\le10^{10}~.

A triangle has angles ~a,b,c~. If it is a valid triangle, print its type, else print INVALID.

The type of the triangle can be ACUTE, RIGHT, or OBTUSE.

Input

The first line contains the number ~n~. The next ~n~ lines contain the numbers ~a,b,c~, separated by a space character.

Output

The answer of the problem.

Sample Input

4
60 60 60
30 60 90
30 120 30
30 30 30

Sample Output

ACUTE
RIGHT
OBTUSE
INVALID

Limits

~n\le50~

~a,b,c\le180~.

A triangle has side lengths ~a,b,c~. If it is a valid triangle, check if it is a right triangle, else print INVALID.

Note: All orientations are counted.

Input

The first line contains the number ~n~. The next ~n~ lines contain the numbers ~a,b,c~, separated by a space character.

Output

The answer of the problem.

Sample Input

3
3 4 5
3 3 3
3 2 1

Sample Output

YES
NO
INVALID

Limits

~n\le50~

~a,b,c\le10^{10}~.

A rectangle has side lengths ~a,b~. Calculate the area of its circumcircle rounded to ~2~ digits of precision.

Assume ~\pi=3.14~.

Input

The first line contains the number ~n~. The next ~n~ lines contain the numbers ~a,b~, separated by a space character.

Output

The answer of the problem.

Sample Input

2
3 4
5 12

Sample Output

19.63
132.67

Limits

~n\le50~

~a,b\le10^{10}~.