/*
可以推测从叶子结点传送到叶子节点才能使传送次数最少，如果是偶数个叶子结点，那么传送leaf/2次就是答案，如果是奇数个叶子结点，则还有单独一条链需要覆盖
dp[u]表示覆盖完u为根的子树需要走的边数，显然在满足传送次数最少的条件下，dp[u]是可以递推的
设以u为根节点，v是u的儿子，如果v就是叶子结点，那么边u->v算一次
如果v中有奇数个叶子节点，那么边u->v只要算一次，因为偶数个叶子结点可以互相配对，然后剩下的叶子结点会从v延伸到u
如果v中有偶数个叶子结点，那么边u->v要算两次
如果叶子结点是偶数，那么dp[1]就是答案，因为任何一颗子树的偶数对叶子结点互相配对，并可以向上延伸
如果叶子结点时奇数，那么某一个叶子结点只要走到岔路口就可以停止了，不用往上走，所以配对时的向上延伸是不必要的
那么找出这么一个叶子结点：其被多算的向上延伸距离是最大的，那么减去被多算的距离就是最优解
那么如果f是那个额外的叶子结点，f向上走到岔路口，从岔路口一直到根，如果u->v被计算了两次，那么因为f是被外挂出来的，所以可以减去一次，
如果u->v只被算了一次，那么要加一次
*/
#include<bits/stdc++.h>
using namespace std;
#define maxn 100005
struct Edge{int to,nxt,cnt;}edge[maxn<<];
int n,ans,leaf,head[maxn],tot;
void init(){
memset(head,-,sizeof head);
tot=;
}
void addedge(int u,int v){
edge[tot].to=v;edge[tot].nxt=head[u];head[u]=tot++;
}
int dfs(int u,int pre){
int cnt=;
for(int i=head[u];i!=-;i=edge[i].nxt){
int v=edge[i].to;
if(v==pre)continue;
edge[i].cnt=dfs(v,u);//访问子树
cnt+=edge[i].cnt;
}
ans+=cnt;
if(cnt==)leaf++;//树叶
if(cnt==||cnt%)return ;
return ;
}
int search(int u,int pre){//返回子树u的最大可以减去的覆盖边数
int mx=;//一定要初始化！其实在岔路口有不往上延伸的选择！、
for(int i=head[u];i!=-;i=edge[i].nxt){
int v=edge[i].to;
if(v==pre)continue;
mx=max(mx,search(v,u)+(edge[i].cnt==?:-));
}
return mx;
}
int main(){
int t,u,v;
cin>>t;
while(t--){
init();
cin>>n;
for(int i=;i<n;i++){
cin>>u>>v;
addedge(u,v);
addedge(v,u);
}
if(n<=){
printf("%d\n",n-);
continue;
}
int root=;
while(edge[head[root]].nxt==-)
root++;//找到非叶子节点的根
leaf=ans=;
dfs(root,);
if(leaf%)ans-=search(root,);
printf("%d\n",ans);
}
}