本文共 6106 字，大约阅读时间需要 20 分钟。

哎今天表现得很差劲，只过了一个题，我希望这是最后一次这么差劲。

You are given a huge integer aa consisting of nn digits (nn is between 11 and 3⋅1053⋅105, inclusive). It may contain leading zeros.

You can swap two digits on adjacent (neighboring) positions if the swapping digits are of different parity (that is, they have different remainders when divided by 22).

For example, if a=032867235a=032867235 you can get the following integers in a single operation:

• 302867235302867235 if you swap the first and the second digits;
• 023867235023867235 if you swap the second and the third digits;
• 032876235032876235 if you swap the fifth and the sixth digits;
• 032862735032862735 if you swap the sixth and the seventh digits;
• 032867325032867325 if you swap the seventh and the eighth digits.

Note, that you can't swap digits on positions 22 and 44 because the positions are not adjacent. Also, you can't swap digits on positions 33 and 44 because the digits have the same parity.

You can perform any number (possibly, zero) of such operations.

Find the minimum integer you can obtain.

Note that the resulting integer also may contain leading zeros.

Input

The first line contains one integer tt (1≤t≤1041≤t≤104) — the number of test cases in the input.

The only line of each test case contains the integer aa, its length nn is between 11 and 3⋅1053⋅105, inclusive.

It is guaranteed that the sum of all values nn does not exceed 3⋅1053⋅105.

Output

For each test case print line — the minimum integer you can obtain.

Example

Input

307091337246432

Output

00791337234642

Note

In the first test case, you can perform the following sequence of operations (the pair of swapped digits is highlighted): 070−−9→0079070_9→0079.

In the second test case, the initial integer is optimal.

In the third test case you can perform the following sequence of operations: 24643−−2→2463−−42→243−−642→234642

这个题目我真的是来来回回做了好长时间，我总觉得自己的代码没有问题，可是上来就是超时，好不容易改了超时的错误就开始出现wa真的是太难了，心态又有点崩，下午仔细总结就发现还是忽略了一点细节，这个题目大意就是，可以交换相邻且奇偶性不同的两个数。若干次这样的操作所能得到的最小值是什么，问题找规律题+贪心，题目要求只有奇偶之间可以换位置，也就是说所有奇数的相对位置是不变的，所有偶数的相对位置也是不变的。那么就开两个数组把奇偶分离，然后，一次输出两个数组中较小的那个就行了。而我忽略了第三种情况，而且在每次开始前数组没有清零。

#include <iostream>#include <fstream>#include <cstdlib>#include <cstring>#include <algorithm>#include <cmath>using namespace std;typedef long long ll;ll t,n;ll b,s,k,x;ll a[10000010];char ch[1000010];ll s1[1000010];ll s2[1000010];int main(){    std::ios::sync_with_stdio(false);    cin.tie(0),cout.tie(0);    cin>>t;    while(t--)    {        string s;        cin>>s;        int len = s.size();        int point1 = 0;        int point2 = 0;        for(int i = 0 ; i < len ; i ++)        {            if((s[i] -'0') %2)                s1[point1++] = s[i];            else                s2[point2++] = s[i];        }        int i = 0,j = 0;        while(i < point1 || j < point2)        {            if(i >= point1)            {                cout<<s2[j++];            }            else if(j >= point2)            {                cout<<s1[i++];            }            else if(s1[i] <= s2[j])            {                cout<<s1[i++];            }            else                cout<<s2[j++];        }        cout<<endl;    }    return 0;}

A palindrome is a string tt which reads the same backward as forward (formally, t[i]=t[|t|+1−i]t[i]=t[|t|+1−i]for all i∈[1,|t|]i∈[1,|t|]). Here |t||t| denotes the length of a string tt. For example, the strings 010, 1001 and 0 are palindromes.

You have nn binary strings s1,s2,…,sns1,s2,…,sn (each sisi consists of zeroes and/or ones). You can swap any pair of characters any number of times (possibly, zero). Characters can be either from the same string or from different strings — there are no restrictions.

Formally, in one move you:

• choose four integer numbers x,a,y,bx,a,y,b such that 1≤x,y≤n1≤x,y≤n and 1≤a≤|sx|1≤a≤|sx| and 1≤b≤|sy|1≤b≤|sy|(where xx and yy are string indices and aa and bb are positions in strings sxsx and sysy respectively),
• swap (exchange) the characters sx[a]sx[a] and sy[b]sy[b].

What is the maximum number of strings you can make palindromic simultaneously?

Input

The first line contains single integer QQ (1≤Q≤501≤Q≤50) — the number of test cases.

The first line on each test case contains single integer nn (1≤n≤501≤n≤50) — the number of binary strings you have.

Next nn lines contains binary strings s1,s2,…,sns1,s2,…,sn — one per line. It's guaranteed that 1≤|si|≤501≤|si|≤50and all strings constist of zeroes and/or ones.

Output

Print QQ integers — one per test case. The ii-th integer should be the maximum number of palindromic strings you can achieve simultaneously performing zero or more swaps on strings from the ii-th test case.

Example

Input

41031110100110010101211111000001200111100111

Output

1222

Note

In the first test case, s1s1 is palindrome, so the answer is 11.

In the second test case you can't make all three strings palindromic at the same time, but you can make any pair of strings palindromic. For example, let's make s1=0110s1=0110, s2=111111s2=111111 and s3=010000s3=010000.

In the third test case we can make both strings palindromic. For example, s1=11011s1=11011 and s2=100001s2=100001.

In the last test case s2s2 is palindrome and you can make s1s1 palindrome, for example, by swapping s1[2]s1[2]and s1[3]s1[3].

题目大意就是给出一些01串，可以交换任意两个串的一个字符。问能得到多少个回文串。解题思路就是首先奇数不用管，因为奇数串中间放什么都可以，所以就把奇数全部变成偶数统计0和1的数目，每次只要放偶数个0和偶数个1就一定行。将0和1都变成偶数（奇数减1）之后，实际上二者等价，你大可合并起来。

#include <cstdio>#include <cstring>#include <algorithm>#include <iostream>using namespace std;int len[1001];int main() {	int t;	cin>>t;	while(t--) {		int n,x = 0,y = 0; 		cin>>n;		for (int i = 1; i <= n; i++) {			char s[100];			cin >> s;			len[i] = strlen(s);			for (int k = 0; k < len[i]; k++)			  if (s[k] == '0') x++;			  else y++;		}		sort(len+1,len+n+1);		int ans = 0;		for (int i = 1; i <= n; i++) {			bool ok = 1;			if (len[i]&1) {				if(x&1) x--;				else {					if(y) y--;					else if(x) x--;					else ok = 0;				}				len[i]--;			}			int t1 = min(x/2,len[i]/2);			x -= t1*2;			len[i] -= t1*2;			int t2 = min(y/2,len[i]/2);			y -= t2*2;			len[i] -= t2*2;			if (len[i]) ok = 0;			if (!ok) break;			ans++;		}		cout<<ans<<endl;	}	return 0;}