Educational Codeforces Round 59 [Rated for Div. 2] A. Digits Sequence Dividing

喜欢ヅ旅行 2022-03-22 07:46 109阅读 0赞

You are given a sequence ss consisting of nn digits from 11 to 99.

You have to divide it into at least two segments (segment — is a consecutive sequence of elements) (in other words, you have to place separators between some digits of the sequence) in such a way that each element belongs to exactly one segment and if the resulting division will be represented as an integer numbers sequence then each next element of this sequence will be strictly greater than the previous one.

More formally: if the resulting division of the sequence is t1,t2,…,tkt1,t2,…,tk, where kk is the number of element in a division, then for each ii from 11 to k−1k−1 the condition ti<ti+1ti<ti+1 (using numerical comparing, it means that the integer representations of strings are compared) should be satisfied.

For example, if s=654s=654 then you can divide it into parts \[6,54\]\[6,54\] and it will be suitable division. But if you will divide it into parts \[65,4\]\[65,4\] then it will be bad division because 65>465>4. If s=123s=123 then you can divide it into parts \[1,23\]\[1,23\], \[1,2,3\]\[1,2,3\] but not into parts \[12,3\]\[12,3\].

Your task is to find any suitable division for each of the qq independent queries.

Input

The first line of the input contains one integer qq (1≤q≤3001≤q≤300) — the number of queries.

The first line of the ii-th query contains one integer number nini (2≤ni≤3002≤ni≤300) — the number of digits in the ii-th query.

The second line of the ii-th query contains one string sisi of length nini consisting only of digits from 11 to 99.

Output

If the sequence of digits in the ii-th query cannot be divided into at least two parts in a way described in the problem statement, print the single line "NO" for this query.

Otherwise in the first line of the answer to this query print "YES", on the second line print kiki — the number of parts in your division of the ii-th query sequence and in the third line print kiki strings ti,1,ti,2,…,ti,kiti,1,ti,2,…,ti,ki — your division. Parts should be printed in order of the initial string digits. It means that if you write the parts one after another without changing their order then you'll get the string sisi.

See examples for better understanding.

Example

input

Copy

4
    6
    654321
    4
    1337
    2
    33
    4
    2122

output

Copy

YES
    3
    6 54 321
    YES
    3
    1 3 37
    NO
    YES
    2
    21 22

> 题目大致的意思是：是否可以将一个串，分成至少两个部分，使得前一个部分的数字大小小于后面的。
> 
> 我们可以得出，当串》=3时，一定可以，当串==2时，分情况讨论。

#include<iostream>
    #include<cstring>
    #include<string>
    using namespace std;
    
    int main()
    {
    	int n,m,j,k,i,T;
    	char s[30000];
    	cin>>T;
    	while (T--)
    	{
    		cin>>n;
    		for (i=0;i<n;i++)
    		cin>>s[i];
    		
    		if (n==2)
    		{
    			if (s[0]>=s[1])
    			{
    				cout<<"NO"<<endl;
    				continue;
    			}
    		}
    		cout<<"YES"<<endl;
    		cout<<2<<endl;
    		cout<<s[0]<<" ";
    		for (i=1;i<n;i++)
    		cout<<s[i];
    		cout<<endl;
    	}
    	
    	return 0;
    }