Farshad wants to do research on friendship relationships between students of the Shahid Beheshti University, so he has decided to model these relations with a graph. In this graph students are numbered from to , every student is represented by a single node, and an edge between node and node means that student number and student number are friends with each other. If is friend with , then is also friend with , and of course no student can be friend with himself. Farshad is interested in doing research on friendship groups (two students and are in a friendship group if and only if and are directly friends with each other or can indirectly connect to each other through friendship links).
Farshad wants to count the number of friendship groups and the number of members each group has. Then HP comes and asks him questions about the number of groups that exist in a particular size range. Each question is of the form , which means HP wants to know the number of all groups that have size greater or equal to and less than or equal to . Help Farshad answer these questions.
The first line of input contains T, the number of test cases. The first line of each test contains three space separated integers where is the number of students, is the number of friendship relations and is the number of questions HP will ask.
Then the next lines each contain two space separated integers . which means student number and student number are friends with each other. Then lines follow, each containing two space separated integers and representing the questions HP will ask.
The output should consist of lines where line number contains the answer to the ’th question.