import math
 
# Đọc dữ liệu nhanh từ input
d = []
try:
    while True:
        d.extend(input().split())
except Exception:
    pass
 
if d:
    p = 0
    t = int(d[p])
    p += 1
 
    for _ in range(t):
        n = int(d[p])
        p += 1
 
        # Sửa lỗi: Thêm phần tử [0] ở đầu mảng
        a = [0] + [int(x) for x in d[p : p + n]]
        p += n
 
        b = [0] + [int(x) for x in d[p : p + n]]
        p += n
 
        # G: Danh sách kề của cây
        G = [[] for _ in range(n + 1)]
        for _ in range(n - 1):
            u, v = int(d[p]), int(d[p + 1])
            p += 2
            G[u].append(v)
            G[v].append(u)
 
        # Sửa lỗi: Khởi tạo mảng cha P và hàng đợi Q = [1]
        P = [0] * (n + 1)
        C = [[] for _ in range(n + 1)]
        Q = [1]
 
        h = 0
        while h < len(Q):
            u = Q[h]
            h += 1
            for v in G[u]:
                if v != P[u]:
                    P[v] = u
                    C[u].append(v)
                    Q.append(v)
 
        # g: Bước nhảy hiệu dụng của mỗi nút
        g = [0] * (n + 1)
        ans = 0
 
        # Duyệt ngược từ lá lên gốc (Bottom-up)
        for u in reversed(Q):
            if not C[u]:
                g[u] = b[u]
            else:
                s = sum(a[v] for v in C[u])
                cur = math.gcd(b[u], s)
                for v in C[u]:
                    # CHỈ TÍNH g[v] NẾU NÚT CON CÓ THỂ BIẾN ĐỔI (g[v] < b[v])
                    if g[v] < b[v]:
                        cur = math.gcd(cur, g[v])
                g[u] = cur
 
            # Tính giá trị lớn nhất đạt được tại nút u và cộng vào kết quả
            ans += b[u] - 1 - ((b[u] - 1 - a[u]) % g[u])
 
        print(ans)
 

aW1wb3J0IG1hdGgKCiMgxJDhu41jIGThu68gbGnhu4d1IG5oYW5oIHThu6sgaW5wdXQKZCA9IFtdCnRyeToKICAgIHdoaWxlIFRydWU6CiAgICAgICAgZC5leHRlbmQoaW5wdXQoKS5zcGxpdCgpKQpleGNlcHQgRXhjZXB0aW9uOgogICAgcGFzcwoKaWYgZDoKICAgIHAgPSAwCiAgICB0ID0gaW50KGRbcF0pCiAgICBwICs9IDEKCiAgICBmb3IgXyBpbiByYW5nZSh0KToKICAgICAgICBuID0gaW50KGRbcF0pCiAgICAgICAgcCArPSAxCgogICAgICAgICMgU+G7rWEgbOG7l2k6IFRow6ptIHBo4bqnbiB04butIFswXSDhu58gxJHhuqd1IG3huqNuZwogICAgICAgIGEgPSBbMF0gKyBbaW50KHgpIGZvciB4IGluIGRbcCA6IHAgKyBuXV0KICAgICAgICBwICs9IG4KCiAgICAgICAgYiA9IFswXSArIFtpbnQoeCkgZm9yIHggaW4gZFtwIDogcCArIG5dXQogICAgICAgIHAgKz0gbgoKICAgICAgICAjIEc6IERhbmggc8OhY2gga+G7gSBj4bunYSBjw6J5CiAgICAgICAgRyA9IFtbXSBmb3IgXyBpbiByYW5nZShuICsgMSldCiAgICAgICAgZm9yIF8gaW4gcmFuZ2UobiAtIDEpOgogICAgICAgICAgICB1LCB2ID0gaW50KGRbcF0pLCBpbnQoZFtwICsgMV0pCiAgICAgICAgICAgIHAgKz0gMgogICAgICAgICAgICBHW3VdLmFwcGVuZCh2KQogICAgICAgICAgICBHW3ZdLmFwcGVuZCh1KQoKICAgICAgICAjIFPhu61hIGzhu5dpOiBLaOG7n2kgdOG6oW8gbeG6o25nIGNoYSBQIHbDoCBow6BuZyDEkeG7o2kgUSA9IFsxXQogICAgICAgIFAgPSBbMF0gKiAobiArIDEpCiAgICAgICAgQyA9IFtbXSBmb3IgXyBpbiByYW5nZShuICsgMSldCiAgICAgICAgUSA9IFsxXQoKICAgICAgICBoID0gMAogICAgICAgIHdoaWxlIGggPCBsZW4oUSk6CiAgICAgICAgICAgIHUgPSBRW2hdCiAgICAgICAgICAgIGggKz0gMQogICAgICAgICAgICBmb3IgdiBpbiBHW3VdOgogICAgICAgICAgICAgICAgaWYgdiAhPSBQW3VdOgogICAgICAgICAgICAgICAgICAgIFBbdl0gPSB1CiAgICAgICAgICAgICAgICAgICAgQ1t1XS5hcHBlbmQodikKICAgICAgICAgICAgICAgICAgICBRLmFwcGVuZCh2KQoKICAgICAgICAjIGc6IELGsOG7m2MgbmjhuqN5IGhp4buHdSBk4bulbmcgY+G7p2EgbeG7l2kgbsO6dAogICAgICAgIGcgPSBbMF0gKiAobiArIDEpCiAgICAgICAgYW5zID0gMAoKICAgICAgICAjIER1eeG7h3QgbmfGsOG7o2MgdOG7qyBsw6EgbMOqbiBn4buRYyAoQm90dG9tLXVwKQogICAgICAgIGZvciB1IGluIHJldmVyc2VkKFEpOgogICAgICAgICAgICBpZiBub3QgQ1t1XToKICAgICAgICAgICAgICAgIGdbdV0gPSBiW3VdCiAgICAgICAgICAgIGVsc2U6CiAgICAgICAgICAgICAgICBzID0gc3VtKGFbdl0gZm9yIHYgaW4gQ1t1XSkKICAgICAgICAgICAgICAgIGN1ciA9IG1hdGguZ2NkKGJbdV0sIHMpCiAgICAgICAgICAgICAgICBmb3IgdiBpbiBDW3VdOgogICAgICAgICAgICAgICAgICAgICMgQ0jhu4ggVMONTkggZ1t2XSBO4bq+VSBOw5pUIENPTiBDw5MgVEjhu4IgQknhur5OIMSQ4buUSSAoZ1t2XSA8IGJbdl0pCiAgICAgICAgICAgICAgICAgICAgaWYgZ1t2XSA8IGJbdl06CiAgICAgICAgICAgICAgICAgICAgICAgIGN1ciA9IG1hdGguZ2NkKGN1ciwgZ1t2XSkKICAgICAgICAgICAgICAgIGdbdV0gPSBjdXIKCiAgICAgICAgICAgICMgVMOtbmggZ2nDoSB0cuG7iyBs4bubbiBuaOG6pXQgxJHhuqF0IMSRxrDhu6NjIHThuqFpIG7DunQgdSB2w6AgY+G7mW5nIHbDoG8ga+G6v3QgcXXhuqMKICAgICAgICAgICAgYW5zICs9IGJbdV0gLSAxIC0gKChiW3VdIC0gMSAtIGFbdV0pICUgZ1t1XSkKCiAgICAgICAgcHJpbnQoYW5zKQo=

OAoxCjMKNwoyCjAgMwo1IDQKMSAyCjMKMCAyIDMKNyAzIDQKMSAyCjIgMwozCjAgMCAxCjUgMiAyCjEgMgoyIDMKNAoxIDIgMyA0CjEwIDMgNCA1CjEgMgoxIDMKMSA0CjMKMCAxIDMKMTAgMiA0CjEgMgoxIDMKNQowIDAgMSAyIDMKMTIgNiA5IDMgNAoxIDIKMSAzCjIgNAozIDUKNAowIDk5OTk5OTk5OSA5OTk5OTk5OTkgOTk5OTk5OTk5CjEwMDAwMDAwMDAgMTAwMDAwMDAwMCAxMDAwMDAwMDAwIDEwMDAwMDAwMDAKMSAyCjEgMwoxIDQK

8
1
3
7
2
0 3
5 4
1 2
3
0 2 3
7 3 4
1 2
2 3
3
0 0 1
5 2 2
1 2
2 3
4
1 2 3 4
10 3 4 5
1 2
1 3
1 4
3
0 1 3
10 2 4
1 2
1 3
5
0 0 1 2 3
12 6 9 3 4
1 2
1 3
2 4
3 5
4
0 999999999 999999999 999999999
1000000000 1000000000 1000000000 1000000000
1 2
1 3
1 4