There are N cups of water which are numbered from 1 to N. The ith cup contains Ai liters of water, and the magical value of the ith cup is Bi.
The 1st operation will pour B1 liters of water from the 1st cup to the 2nd cup.
The Nth operation will pour BN liters of water from the Nth cup to the 1st cup.
The (N + 1)th operation will pour B1 liters of water from the 1st cup to the 2nd cup.
......
If the water in the cup is not enough to perform the operation, the game will stop immediately. The question is if this game will keep running forever? If not, how many times will it be operated?
The first line contains an integer T, where T is the number of test cases. T test cases follow.
For each test case, the first line contains one integer N, where N is the number of cups.The second line contains N integers A1, A2, ... , AN, where Ai is the volume of water in the ith cup.The third line contains N integers B1, B2, ... , BN, where Bi is the magical value of the ith cup.
For each test case, output one line containing “Case #x: y”, where x is the test case number (startingfrom 1). If the game will keep running forever, y is “INF”. Otherwise, y is the operation times.• 1 ≤ T ≤ 102.• 2 ≤ N ≤ 102.• 0 ≤ Ai ≤ 109.• 1 ≤ Bi ≤ 109.
For the first case, this game’s operation times is 7.
[4,5,6] ⇒ [3,6,6] ⇒ [3,3,9] ⇒ [9,3,3] ⇒ [8,4,3] ⇒ [8,1,6] ⇒ [14,1,0] ⇒ [13,2,0]
For the second case, this game will keep running forever.