有 个结点，第 个结点的权值为 。 初始时都为孤立的点，互不连通。 现在需要加若干条无向边，使得所有点构成一张无向连通图。 我们定义在两个结点之间加边的代价为：如果两个点的权值都是偶数或者都是奇数，代价为 。否则为 。 现在你需要帮助算出所有点构成一张无向连通图的最小代价之和。 注：加边过程中不能有重边和自环。

输入描述:

第一行一个整数  ,表示输入的数据组数。对于每组数据的格式为：第一行三个整数 ，表示结点个数和连通结点的不同代价。第二行  个整数，第  个数 表示第  个结点的权值。对于单组数据保证 。

输出描述:

共  行，每行 一个整数，表示所有点构成一张无向连通图的最小代价之和。