题目描述

某地建设了一套由 $n$ 个通信终端组成的有线网络，终端编号为 $1\sim n$。网络中任意两个终端之间都能够通信，并且它们之间的通信路线唯一，因此整个网络构成一棵树。

对于一个编号区间 $[l,r]$，考虑所有编号位于该区间内的终端。若一条网络线路 $(u,v)$ 满足：存在两个终端 $i,j$，其中 $l\le i<j\le r$，并且终端 $i$ 与终端 $j$ 之间的唯一通信路线经过线路 $(u,v)$，则称这条线路被区间 $[l,r]$ 激活。

定义区间 $[l,r]$ 的通信强度为被该区间激活的网络线路数量。

现在有 $q$ 次询问。每次询问给出 $l,r$，你需要枚举所有满足 $l\le i<j\le r$ 的编号子区间 $[i,j]$，并求这些子区间通信强度的总和。

输入格式

第一行包含一个正整数 $n$，表示通信终端数量。

接下来 $n$ 行，每行两个正整数 $u,v$，表示终端 $u$ 与终端 $v$ 之间有一条网络线路。

第 $n+1$ 行包含一个正整数 $q$，表示询问次数。

接下来 $q$ 行，每行两个正整数 $l,r$，表示一次询问。

输出格式

共 $q$ 行，每行一个正整数，表示询问的答案。

样例

样例 1 输入

    6
    2 1
    2 6
    2 3    
    4 3
    2 5
    6
    3 5
    3 5
    4 5
    1 6
    2 3
    2 6

样例 1 输出

    7
    7
    3
    42
    1
    27

数据范围与提示

保证对于所有的测试点满足以下限制：$1\leq n,q\leq 10^5,1\leq u,v\leq n,1\leq l\leq r\leq n$。

特殊性质A：保证给定的树是一条链。

特殊性质B：保证存在一个点的度数为 $n-1$。