You might already know that Ada the Ladybug has some friends who live on a plum tree. Those friends are numbered from 1 to N (where N is the number of her friends). Ada freely travels on the tree from one friend to another. As she passes a friend (with ID i), he/she always tells her "Hey Ada! If you meet i+1 or i-1, please give him my phone number.". Also note that as long as someone obtains phone number of someone else, he distributes it to all friends whose number he/she has.

Ada will undertake many walks on the tree (from one friend to another) and she ask you (for each walk), how many independent sets of friends she will make during her walk. The two sets are independent if nobody from one set has a number of someone else in the other set (and vice versa).

NOTE: All walks are independent of each other (so no phone-distribution remains from previous walks).

Input

The first line will contain two integers 1 ≤ N, Q ≤ 2*10⁵, the number of Ada's friends and the number of walks

The next N-1 lines will contain two integers 1 ≤ a, b ≤ N, meaning that there is a branch (edge) between a^th and b^th friend.

The next Q lines will contain two integers 1 ≤ a, b ≤ N, meaning that Ada will take walk between a^th and b^th friend.

Output

For each query, print the number of independent sets Ada will create by her walk (counting only friends on her path).

Example Input

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

Example Output

3
1
2
2
2
1

Example Input 2

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

Example Output 2

2
2
2
3
2

Example Input 3

10 10
7 10
2 10
4 10
1 7
8 7
3 10
9 10
5 8
6 2
4 3
7 7
2 5
7 8
7 6
5 2
4 9
7 3
9 6
8 8

Example Output 2

2
1
4
1
3
4
2
3
3
1