T = int(input())
inf = int(2e18)
for _ in range(T):
    N, M, K = map(int, input().split())
    x = [0]*M
    y = [0]*M
    for i in range(M):
        x[i], y[i] = map(int, input().split())
    cnt = [0]*N
    mem = [0]*N
    for i in range(M):
        x[i] -= 1
        cnt[x[i]] += 2
        # (x-y)^2-(x-(y-1))^2 = 2x-2y-1
        mem[x[i]] -= 2*y[i]+1
    left = -inf
    right = inf
    while left+1 < right:
        mid = (right+left)//2
        cnt2 = 0
        for i in range(N):
            if cnt[i] == 0:
                if 0 <= mid:
                    cnt2 += inf
            else:
                # ax+mem[i] ≤ mid
                # ax ≤ mid-mem[i]
                cnt2 += max(0, (mid-mem[i])//cnt[i])
            if cnt2 > K:
                break
        if cnt2 <= K:
            left = mid
        else:
            right = mid
    ans = 0
    flag = False
    num = [0]*N
    cnt2 = 0
    for i in range(N):
        if cnt[i] == 0:
            flag = True
        else:
            num[i] = max(0, (left-mem[i])//cnt[i])
            cnt2 += num[i]
    for i in range(M):
        ans += (num[x[i]]-y[i])*(num[x[i]]-y[i])
    if flag and right > 0:
        cnt2 = K
    ans += (K-cnt2)*right
    print(ans)