import sys

def solve() -> None:
    it = iter(sys.stdin.read().strip().split())
    t = int(next(it))
    out_lines = []
    for _ in range(t):
        n = int(next(it))
        q = int(next(it))
        a = [int(next(it)) for _ in range(n)]
        b = [int(next(it)) for _ in range(n)]
        # c[i] = max(a[i], b[i])
        c = [max(ai, bi) for ai, bi in zip(a, b)]
        # suffix maxima M[i] = max_{j>=i} c[j]
        M = [0] * n
        M[-1] = c[-1]
        for i in range(n-2, -1, -1):
            M[i] = max(c[i], M[i+1])
        # prefix sums of M
        pref = [0] * (n + 1)
        for i in range(n):
            pref[i+1] = pref[i] + M[i]
        # answer queries
        ans = []
        for __ in range(q):
            l = int(next(it))
            r = int(next(it))
            ans.append(str(pref[r] - pref[l-1]))
        out_lines.append(" ".join(ans))
    sys.stdout.write("\n".join(out_lines))

if __name__ == "__main__":
    solve()

import sys

# Function to calculate the sum of digits of a number
def get_digit_sum(n):
    s = 0
    while n > 0:
        s += n % 10
        n //= 10
    return s

def solve():
    # Read all input from standard input
    input_data = sys.stdin.read().split()
    
    if not input_data:
        return

    iterator = iter(input_data)
    try:
        # First token is the number of test cases
        t = int(next(iterator))
    except StopIteration:
        return

    results = []
    
    for _ in range(t):
        try:
            x = int(next(iterator))
        except StopIteration:
            break
            
        count = 0
        # We are looking for y such that y - d(y) = x.
        # This can be rewritten as y = x + d(y).
        # Let s = d(y). Then y = x + s.
        # We need to check if d(x + s) == s.
        # Since x <= 10^9, y is roughly 10^9.
        # The maximum sum of digits for a number <= 10^9 + 100 is 81 (for 999,999,999).
        # Thus, s will not exceed 90. We iterate s from 1 to 100 to be safe.
        
        for s in range(1, 100):
            y = x + s
            if get_digit_sum(y) == s:
                count += 1
        
        results.append(str(count))
    
    # Print all results separated by newlines
    print('\n'.join(results))

if __name__ == '__main__':
    solve()