Modulo Equality

All submissions for this problem are available.
You have two arrays A and B, each containing N integers.
Elements of array B cannot be modified.
You may perform an arbitrary number of operations (including zero number of operations). In one operation, you can choose one index i (1 ≤ i ≤ N) and increment A_{i} by 1. Each index can be chosen any number of times.
Find the minimum number of operations required to modify the array A such that for every pair i, j (1 ≤ i, j ≤ N), (A_{i} % B_{i}) equals (A_{j} % B_{j}). Here, % denotes the modulo operator (the remainder after dividing by B_{i}). Note that 0 ≤ (A_{i} % B_{i}) < B_{i}.
Input
First line of the input contains an integer T denoting the number of testcases. The description of T testcases is as follows:
First line of each testcase contains a positive integer N, denoting the number of elements in arrays A and B.
Second line contains N spaceseparated whole numbers A_{1}, A_{2}, ..., A_{N}.
Third line contains N spaceseparated natural numbers B_{1}, B_{2}, ..., B_{N}.
Output
For each testcase, output a single line containing the minimum number of operations required to modify the array A in order to satisfy the required conditions.
Constraints
 1 ≤ T ≤ 1000
 1 ≤ N ≤ 5 * 10^{5}
 0 ≤ A_{i} ≤ 10^{9}
 1 ≤ B_{i} ≤ 10^{9}
 Sum of N across all testcases in a single file will be ≤ 5 * 10^{5}
Example
Input: 2 3 4 2 2 5 3 4 4 2 1 1 2 3 3 3 3 Output: 3 2
Explanation
Example case 1. A_{1} can be increased from 4 to 7 in 3 operations so that:
 A_{1} % B_{1} = 2
 A_{2} % B_{2} = 2
 A_{3} % B_{3} = 2
Example case 2. A_{2}, A_{3} can both be increased from 1 to 2 in 2 operations total so that:
 A_{1} % B_{1} = 2
 A_{2} % B_{2} = 2
 A_{3} % B_{3} = 2
 A_{4} % B_{4} = 2
Author:  wittyceaser 
Tags  acmind17, easymedium, prefixsum, wittyceaser 
Date Added:  29102017 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, PYP3 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 