背景故事

在人世间流传着这样一个传说，传说中妖族大帝duck大魔王曾在世间留下过7份宝藏，每一个宝藏都有着化腐朽为神奇的力量 —— 能让枯萎千年的古木重新绽放花苞，能将断裂的青铜古剑熔铸成斩破云层的神兵，甚至能让干涸的死海凭空涌出带着荧光的灵泉。没人见过这位大帝的真容，只知道古籍里画着他头顶两撮雪白的鸭绒，手持镶嵌红宝石的黄金鸭掌权杖，连踏过的地方都会长出带着 “鸭掌纹” 的七彩苔藓。

叶梓楣第一次听说这个传说时，正蹲在村口药庐的灶台前烧火。他是个再普通不过的凡人，从有记忆起，就跟着魂师先生打杂糊口，看着先生用粗浅的丹药治好村民的小病，心里总藏着个不敢说的念头 —— 她想修行。可凡人没有灵根，连最低阶的练气都学不会，先生曾摸着他的头叹气：“梓楣，凡人有凡人的活法，别想那些遥不可及的事。

”可叶梓楣虽无统广袤天地之伟愿，但却也想看看这人间种种，毕竟在这世间普通人可能一辈子也走不出所在的村庄，哪怕是到处行商之人，走的也不过是世界的偏隅一角，可是虽有心而力不足啊，我一凡人又哪敢走出村子，银两暂且不谈，光是这覆雪苍山，阻隔南北一界，便让人难以虹越，梓楣越想越是难过，也顾不上烧火，边走边叹，回到了自己的房中。

魂师先生看着梓楣的落魄的背影，忽是想到了些什么，顾不上炉中的丹药，拿起一把铲子就朝院子的银杏树跑去，一炷香后，捧着一个包裹严实的盒子叹道:"还好，还好，没有什么事，这年纪大了，差点就忘记了当初的那张纸条。"其实这梓楣并非是老先生亲戚家的孩子，这是老先生在那年大雪中捡到的孩子，老先生看孩子这么小在这天寒地冻之下，只身只有一襁褓披挂，身上还发着高烧，于是心生怜悯，便带回家，想着待风雪过去 ，稍些时日就去寻找这孩子的娘亲，可哪知，这雪一下就是三月，不过老先生也未曾放弃，但随着时间一点点的推移，岁月也不曾饶人，时光在老先生的皮肤上留下了深深的褶皱，就像是泡发的陈皮，这件事情也不了了之，不过当初见到这孩子的时候，他的身上有着一封信，一个盒子，还有一节碎玉，不知是不是其亲生父母所留，信上所说，这盒子是留给梓楣的，不过在成年之前，不要打开这个盒子。

而今便是梓楣成年的日子啊，这小家伙也是长大了， 身七尺男儿、才高八斗，立在那里，便引得无数行人过客不经再多看一眼，肩线开阔却不沉赘，走路时脊背挺得笔直，步子迈得轻快，像有春风裹着衣角，连落在地面的影子都带着股蓬勃的劲儿。不似成人那般棱角锋利，肩头还留着点少年特有的单薄，可抬手拂过额前碎发时，手腕转动的弧度里，又藏着不卑不亢的利落。五官不算惊艳，却胜在眉眼清亮。眉峰微微上扬，像墨笔轻描的一道锋，不浓不密，却衬得那双眼睛格外有神。魂师先生虽称不上镇上的大富大贵，但也是有着稳定收入，拥有着一个青砖黛瓦的小院，梓楣这孩子从小好读书，魂师先生虽给不了什么锦衣玉食，不过书还是管够的，梓楣凡有所求，魂师先生必会做到，这使得梓楣从小就饱读诗书，谈吐中字字都裹着书卷的清润气，身上总带着股淡淡的墨香，心中总想着大道，这是属于18岁少年的气息。

梓楣，梓楣，快出来看看，我有东西要给你，老先生虽保存这盒子18年，但也未曾打开看过，今日按照信上所写，把这东西交给梓楣。“这是当初我捡到你时，你身上所带的盒子，当时还有一封信和你现在所带的碎玉，信中让我在你成年时交给你，快打开看看吧，莫不是有什么重要的东西，也许会有你亲生父母的线索呢”，梓楣接过盒子，眼神中闪烁着激动，紧张，害怕等复杂的情绪，这里面会有什么呢，打开这个盒子，我不会就要离老先生而去了吧，真的，真的，会有我家人的线索吗。 梓楣迟疑良久，双手环抱着箱子迟迟没有打开，这时老先生浑厚有力的大手拍在了梓楣的肩上，快打开看看吧孩子，万一有很重要的东西了，天地因缘，总是躲不过去的，你不是一直想知道自己的身世吗。“先生，我不在乎的，我想一直陪着你”梓楣小声的嘟囔道，老先生哈哈大笑，好啊你有这份心，我呀就满足了，好了快打开看看吧。 梓楣下定决心，打开了尘封以久的盒子，盒中许是封存了太多年月，开盖时便有淡淡的檀香漫出来，混着一点潮湿的古木气息，像老先生药庐里那捆压了十年的沉香木。叶梓楣的指尖还沾着火山灰，刚碰到盒沿就顿住 —— 在檀木盒中央，竟静静躺着张巴掌大的残卷地图，边缘被虫蛀得毛边，可地图上的纹路却裹着层细碎的金光，像把星星揉碎了撒在上面。梓楣的指尖还带着灶台的炭灰，刚碰到盒沿就猛地缩了缩 —— 不是烫，是那缕檀香裹着的金光太暖，像先生冬夜捂在他手里的暖炉，顺着指尖往心口钻。他低头盯着那卷残图，虫蛀的毛边下，金光勾勒出的纹路竟慢慢动了起来：一处画着缠满枯藤的沼泽（像传说里藏着青铜鸭首壶的雾隐沼泽），一处标着冒火的火山（正是焚天火山的模样），还有个模糊的冰棱标记，边角处隐约能看见 “倒悬” 二字的残笔。

“这…… 这是……” 他的声音发颤，指腹轻轻蹭过地图中央，突然，掌心传来一阵细微的麻痒 —— 那道平日戴在脖子上的碎玉，竟隔着衣裳发烫，像有什么东西在和地图里的金光呼应。

老先生凑过来，浑浊的眼睛在看到地图背面朱砂鸭掌纹时，突然亮了：“这是！当年捡你时，襁褓里除了盒子和信，还有块碎玉，上面的纹路和这个一模一样！” 随着与碎玉的靠近，地图的字迹也慢慢清晰，地图上，在一个地点标注着宝藏的标识，梓楣攥着玉片的手沁出了汗，突然想起先生曾说 “凡人想修行，如石中种莲”，可此刻地图的金光映在他眼底，连之前因 “走不出村庄” 而生的沮丧，都像被檀香吹散了：“先生，这地图…… 难道和 duck 大魔王的宝藏有关？”

老先生摸着下巴的白须，眼神沉了沉：“当年信上只说‘此盒系梓楣命数所系，成年后方可开启’，我原以为只是寻常信物，可现在看来…… 你爹娘或许和这些宝藏，甚至那位妖族大帝，都有关系。” 他拍了拍梓楣的肩，指腹蹭过梓楣腕间因挑水磨出的茧，“你不是想看看这人间吗？不是想修行吗？这地图，就是你的路。”

梓楣望着地图上跳动的金光，又看了看先生鬓角的白发 —— 他突然想起小时候先生冒雪为他寻退烧药，想起药庐里永远温着的粥，鼻子一酸：“可我走了，先生你……”

“傻孩子，” 老先生笑了，从袖袋里摸出个布包塞进他手里，里面是晒干的清凉草、几瓶暖身药，还有那捆压了十年的沉香木，“你不能守着这药庐一辈子，也该让你去闯闯了。再说，你带着这玉片，带着这地图，说不定还能找到你的爹娘。”

话音刚落，地图上的金光突然暴涨，一缕金芒顺着梓楣的指尖缠上后颈 —— 他慌忙摸去，那道鸭掌纹竟然跑到了脖颈后，和地图背面的朱砂纹、玉片的纹路，一模一样！

“这是…… 鸭纹持有者的标记？” 梓楣愣住了，突然想起传说里 “鸭纹持有者能引动宝藏” 的说法，心脏狂跳起来。

老先生也惊了，随即叹了口气，他把木盒递给梓楣，“把地图收好，路上小心有心之人，这一路上可不太平啊，老头我啊，将朽之木，也帮不到你什么了，多加保重啊，梓楣。“

梓楣把地图塞进贴身处的布袋，又将沉香木抱在怀里，突然对着老先生跪了下去，磕了三个响头：“先生，等我找到宝藏，学会修行，一定回来陪您！”

老先生连忙扶起他，眼眶微红：“好，好，我在药庐等你，给你留着粥。”

梓楣站起身，脊背挺得笔直，像先生说的 “有春风裹着衣角”—— 他低头看了看布袋里隐隐发烫的地图，又望了望村口那条通往远方的小路，突然笑了：覆雪苍山又如何？没有灵根又如何？这一次，他终于有了走出村庄的勇气，有了触碰 “遥不可及” 的机会。

而他没看见的是，在他转身离开时，老先生从袖袋里摸出另一张泛黄的纸条，上面画着和梓楣后颈一样的鸭掌纹，落款处是两个模糊的字：“鸭帝”。老先生望着梓楣的背影，轻声呢喃：“当年的承诺，总算能兑现了……”

题目描述

叶梓楣到达了，第一处宝藏的所在地，但要想得到宝藏，必须解决这问题。

给定一个长度为n的整数数组a。你可以对数组a应用以下操作，可以零次或多次：

• 选择数组ai​和aj​中的两个不同的数；
• 从数组中删除第i个和第j个元素。

对于应用一些操作序列后的数组，最小可能的数字大小是多少？

Input

第一行将会包含一个整数T（1<=t<=1e4）,表示测试的数量。 每个测试用例的第一行包含一个整数n（1<=n<=2e5）,表示数组a的长度。 每个测试用例的第二行包含n个整数a1,a2,…,an（1<=ai<=1e9）。 保证所有测试用例中n的总和不超过2e5

Output

对于每个测试用例，输出应用一些操作序列后数组的最小可能大小。

Samples

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

0
0
2
1
0

Limitation

1s, 1024KiB for each test case.