Problem Statement

A shop sells a product whose regular price is A yen (Japanese currency) for B yen. By what percentage of the regular price is this product discounted?

Constraints

• A and B are integers.
• 1 ≤ B < A ≤ 10^5

Sample Input 1

100 80

Sample Output 1

20.0

If a product whose regular price is 100 yen is sold for 80 yen, it is discounted by 20 percent of the regular price.

Sample Input 2

7 6

Sample Output 2

14.285714285714285714

Sample Input 3

99999 99998

Sample Output 3

0.00100001000010000100

Problem Statement

Takahashi wants to buy the popular video game console called Play Snuke.
There are N shops that sell Play Snuke: Shop 1, 2, \dots, N. Shop i is A_i minutes' walk from where Takahashi is now, sells Play Snuke for P_i yen (Japanese currency), and currently has X_i Play Snukes in stock.
Now, Takahashi will go to one of those shops on foot and buy Play Snuke if it is still in stock when he gets there.
However, Play Snuke is so popular that the number of consoles in stock (if any) in every shop will decrease by 1 at the following moments: 0.5, 1.5, 2.5, \dots minutes from now.
Determine whether Takahashi can buy Play Snuke. If he can, find the minimum amount of money needed to buy one.

Constraints

• All values in input are integers.
• 1 ≤ N ≤ 10^5
• 1 ≤ A_i, P_i, X_i ≤ 10^9

Sample Input 1

3
3 9 5
4 8 5
5 7 5

Sample Output 1

8

If he goes to Shop 1, it will still have 2 Play Snukes when he gets there, and he can buy one for 9 yen.
If he goes to Shop 2, it will still have 1 Play Snuke when he gets there, and he can buy one for 8 yen.
If he goes to Shop 3, Play Snuke will be out of stock when he gets there; he cannot buy one.

Sample Input 2

3
5 9 5
6 8 5
7 7 5

Sample Output 2

-1

Sample Input 3

10
158260522 877914575 602436426
24979445 861648772 623690081
433933447 476190629 262703497
211047202 971407775 628894325
731963982 822804784 450968417
430302156 982631932 161735902
880895728 923078537 707723857
189330739 910286918 802329211
404539679 303238506 317063340
492686568 773361868 125660016

Sample Output 3

861648772

Problem Statement

Given is an integer N. How many integers between 1 and N (inclusive) are unrepresentable as a^b, where a and b are integers not less than 2?

Constraints

• N is an integer.
• 1 ≤ N ≤ 10^{10}

Sample Input 1

8

Sample Output 1

6

4 and 8 are representable as a^b: we have 2^2 = 4 and 2^3 = 8.
On the other hand, 1, 2, 3, 5, 6, and 7 are unrepresentable as a^b using integers a and b not less than 2, so the answer is 6.

Sample Input 2

100000

Sample Output 2

99634

Problem Statement

We have 9K cards. For each i = 1, 2, \dots, 9, there are K cards with i written on it.
We randomly shuffled these cards and handed out five cards - four face up and one face down - to each of Takahashi and Aoki.
You are given a string S representing the cards handed out to Takahashi and a string T representing the cards handed out to Aoki.
S and T are strings of five characters each. Each of the first four characters of each string is 1, 2, \dots, or 9, representing the number written on the face-up card. The last character of each string is #, representing that the card is face down.
Let us define the score of a five-card hand as \displaystyle \sum_{i=1}^9 i \times 10^{c_i}, where c_i is the number of cards with i written on them.
Takahashi wins when the score of Takahashi's hand is higher than that of Aoki's hand.
Find the probability that Takahashi wins.

Constraints

• 2 ≤ K ≤ 10^5
• |S| = |T| = 5
• The first through fourth characters of each of S and T are 1, 2, \dots, or 9.
• Each of the digit 1, 2, \dots, and 9 appears at most K times in total in S and T.
• The fifth character of each of S and T is #.

Sample Input 1

2
1144#
2233#

Sample Output 1

0.4444444444444444

For example, if Takahashi's hand is 11449 and Aoki's hand is 22338, Takahashi's score is 100+2+3+400+5+6+7+8+90=621 and Aoki's score is 1+200+300+4+5+6+7+80+9=612, resulting in Takahashi's win.
Takahashi wins when the number on his face-down card is greater than that of Aoki's face-down card, so Takahashi will win with probability \frac49.

Sample Input 2

2
9988#
1122#

Sample Output 2

1.0

Sample Input 3

6
1122#
2228#

Sample Output 3

0.001932367149758454

Takahashi wins only when Takahashi's hand is 11222 and Aoki's hand is 22281, with probability \frac2{1035}.

Sample Input 4

100000
3226#
3597#

Sample Output 4

0.6296297942426154

Problem Statement

A train goes back and forth between Town A and Town B. It departs Town A at time 0 and then repeats the following:

• goes to Town B, taking X seconds;
• stops at Town B for Y seconds;
• goes to Town A, taking X seconds;
• stops at Town A for Y seconds.

More formally, these intervals of time are half-open, that is, for each n = 0, 1, 2, \dots:

• at time t such that (2X + 2Y)n ≤ t < (2X + 2Y)n + X, the train is going to Town B;
• at time t such that (2X + 2Y)n + X ≤ t < (2X + 2Y)n + X + Y, the train is stopping at Town B;
• at time t such that (2X + 2Y)n + X + Y ≤ t < (2X + 2Y)n + 2X + Y, the train is going to Town A;
• at time t such that (2X + 2Y)n + 2X + Y ≤ t < (2X + 2Y)(n + 1), the train is stopping at Town A.

Takahashi is thinking of taking this train to depart Town A at time 0 and getting off at Town B. After the departure, he will repeat the following:

• be asleep for P seconds;
• be awake for Q seconds.

Again, these intervals of time are half-open, that is, for each n = 0, 1, 2, \dots:

• at time t such that (P + Q)n ≤ t < (P + Q)n + P, Takahashi is asleep;
• at time t such that (P + Q)n + P ≤ t < (P + Q)(n + 1), Takahashi is awake.

He can get off the train at Town B if it is stopping at Town B and he is awake.
Determine whether he can get off at Town B. If he can, find the earliest possible time to do so.
Under the constraints of this problem, it can be proved that the earliest time is an integer.

You are given T cases. Solve each of them.

Constraints

• All values in input are integers.
• 1 ≤ T ≤ 10
• 1 ≤ X ≤ 10^9
• 1 ≤ Y ≤ 500
• 1 ≤ P ≤ 10^9
• 1 ≤ Q ≤ 500

Sample Input 1

3
5 2 7 6
1 1 3 1
999999999 1 1000000000 1

Sample Output 1

20
infinity
1000000000999999999

Let [a, b) denote the interval a ≤ t < b.

In the first case, the train stops at Town B during [5, 7), [19, 21), [33, 35), \dots, and Takahashi is awake during [7, 13), [20, 26), [33, 39), \dots, so he can get off at time 20 at the earliest.

Problem Statement

We have a grid with N horizontal rows and N vertical columns.
Let (i, j) denote the square at the i-th row from the top and j-th column from the left. A character c_{i,j} describes the color of (i, j).
B means the square is painted black; W means the square is painted white; ? means the square is not yet painted.

Takahashi will complete the black-and-white grid by painting each unpainted square black or white.
Let the zebraness of the grid be the number of pairs of a black square and a white square sharing a side.
Find the maximum possible zebraness of the grid that Takahashi can achieve.

Constraints

• 1 ≤ N ≤ 100
• c_{i, j} is B, W, or ?.

Sample Input 1

2
BB
BW

Sample Output 1

2

We have two pairs of a black square and a white square sharing a side: (1, 2), (2, 2) and (2, 1), (2, 2), so the zebraness of this grid is 2.

Sample Input 2

3
BBB
BBB
W?W

Sample Output 2

4

Painting (3, 2) white makes the zebraness 3, and painting it black makes the zebraness 4.

Sample Input 3

5
?????
?????
?????
?????
?????

Sample Output 3

40