Little Q is playing an RPG game. In this game, the weapon can be upgraded. Initially, the weapon is at level 00, and the upper bound of the level is n. Assume the current level is ii (0≤i<n), Little Q can pay ci coins to upgrade the weapon, the next level will be i+1iwith probability pi, and will be i-j(1≤j≤i) with probability ∑k=1iwkwj.
Though Little Q is very rich, he is still wondering the expected number of coins for him to upgrade the weapon from level 00 to level n. Please write a program to help him.
The first line contains a single integer T(1≤T≤300), the number of test cases. For each test case:
The first line contains a single integer n (2≤n≤100,000), denoting the upper bound of the level.
The ith (1≤i≤n) of the following n lines contains two integersPi−1 andci−1 (1≤Pi−1,ci−1≤100), describing the success probability and the cost for level i-1i−1. Here pi−1=100Pi−1. It is guaranteed thatP0=100.
The next line contains n-1 integers w1,w2,…,wn−1 (1≤wi≤100).
It is guaranteed that the sum of all n is at most 500,000.
For each test case, output a single line containing an integer, denoting the expected number of coins to level n
More precisely, if the answer is P/Q, you should output the minimum non-negative integer rsuch that q⋅r≡p(mod998,244,353). You may safely assume that such r always exists in all test cases.
2
2
100 1
50 5
1
3
100 1
70 2
50 3
2 312
228170152