Alice and Bob are playing a strange game using coins.
Initially, Alice has coins, and Bob has coins. They take turns choosing one of the following options, starting with Alice:

1. Try to double it. With probability , his/her coin gets doubled up, and with the remaining probability, he/she loses all the coins and the game immediately.
2. Pass to the next person. This literally means doing nothing in his/her turn. This operation costs coins and is only possible when he/she has more than coins

A player loses the game if he/she loses all his coins. Determine the probability that Alice wins if both players act optimally.

输入描述:

The first line contains an integer  , denoting the number of test cases.

For each test case, the only line contains four integers   such that the parameter of the game is set as .

输出描述:

For each test case, output an integer in a line, denoting the probability that Alice wins if both players act optimally. Under the input constraints of this problem, it can be shown that the answer can be written as , where  and  are coprime integers and . You need to output  as an answer, where  is the modular inverse of  with respect to .

1
100 100 10 20

166374059