History - ADAPET

Test - ADAPET

ADAPET

	1 bbaabbba 2
	1 abababbababbbbbaaabbaaaba 1000000
	1 abababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaaba 1000000
	1 abababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaababbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaababbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabab 1000000
	1 abababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaababbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaababbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaababbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaababbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaab 1000000
	1 aaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaab 1000000
	1 bbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaab 1000000
	1 aabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaab 1000000
	1 aaabaabababbababbbbbaaabbaaabaabababbababbbbbaaab 1000000
	1 bbababbbbbaaabbaaabaabababbababbbbbaaab 1000000
	1 bbbaaabbaaabaabababbababbbbbaaab 1000000
	1 acacac 1000000
	1 acabac 1000000
	1 acacabacacabacacac 1000000
	1 acabac 1000000
	1 aaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaab 1000000 bbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaab 1000000 aabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaab 1000000 aaabaabababbababbbbbaaabbaaabaabababbababbbbbaaab 1000000 bbababbbbbaaabbaaabaabababbababbbbbaaab 1000000 bbbaaabbaaabaabababbababbbbbaaab 1000000 acacac 1000000 acabac 1000000 acacabacacabacacac 1000000
	9 aaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaab 1000000 bbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaab 1000000 aabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaab 1000000 aaabaabababbababbbbbaaabbaaabaabababbababbbbbaaab 1000000 bbababbbbbaaabbaaabaabababbababbbbbaaab 1000000 bbbaaabbaaabaabababbababbbbbaaab 1000000 acacac 1000000 acabac 1000000 acacabacacabacacac 1000000
	1 bbaabbba 2
	1 gorgeo 2
	9 aaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaab 1000000 bbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaab 1000000 aabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaab 1000000 aaabaabababbababbbbbaaabbaaabaabababbababbbbbaaab 1000000 bbababbbbbaaabbaaabaabababbababbbbbaaab 1000000 bbbaaabbaaabaabababbababbbbbaaab 1000000 acacac 1000000 acabac 1000000 acacabacacabacacac 10000000000
	9 aaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaab 1000000 bbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaab 1000000 aabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaab 1000000 aaabaabababbababbbbbaaabbaaabaabababbababbbbbaaab 1000000 bbababbbbbaaabbaaabaabababbababbbbbaaab 1000000 bbbaaabbaaabaabababbababbbbbaaab 1000000 acacac 1000000 acabac 1000000 acacabacacabacacac 100000000
	1 abcabcabcabc 4
	9 aaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaab 10 bbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaab 1000000 aabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaab 10 aaabaabababbababbbbbaaabbaaabaabababbababbbbbaaab 10 bbababbbbbaaabbaaabaabababbababbbbbaaab 1000000 bbbaaabbaaabaabababbababbbbbaaab 1000000 acacac 1000000 acabac 1000000 acacabacacabacacac 1000000
	1 bbbaaabbaaabaabababbababbbbbaaab 2
	1 bbbaaabaaab 2
	1 bbbaaabbabaabababbababbbbbaaab 2
	10 aaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaab 1000000 bbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaab 1000000 aabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaab 1000000 aaabaabababbababbbbbaaabbaaabaabababbababbbbbaaab 1000000 bbababbbbbaaabbaaabaabababbababbbbbaaab 1000000 bbbaaabbaaabaabababbababbbbbaaab 1000000 acacac 1000000 acabac 1000000 acacabacacabacacac 1000000
	2 bb 10032 a 1000000
	1 acacac 1000000
	1 abababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaaba 1000000
	1 abababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaababbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaababbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabab 1000000
	9 aaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaab 1000000 bbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaab 1000000 aabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaab 1000000 aaabaabababbababbbbbaaabbaaabaabababbababbbbbaaab 1000000 bbababbbbbaaabbaaabaabababbababbbbbaaab 1000000 bbbaaabbaaabaabababbababbbbbaaab 1000000 acacac 1000000 acabac 1000000 acacabacacabacacac 1000
	1 acacabacacabacacac 10000000000
	10 aaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaab 1000000 bbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaab 1000000 aabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaab 1000000 aaabaabababbababbbbbaaabbaaabaabababbababbbbbaaab 1000000 bbababbbbbaaabbaaabaabababbababbbbbaaab 1000000 bbbaaabbaaabaabababbababbbbbaaab 1000000 acacac 1000000 acabac 1000000
	10 aaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaab 1000000 bbababbbbbaaabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaab 1000000 aabbaaabaabababbababbbbbaaabbaaabaabababbababbbbbaaab 1000000 aaabaabababbababbbbbaaabbaaabaabababbababbbbbaaab 1000000 bbababbbbbaaabbaaabaabababbababbbbbaaab 1000000 bbbaaabbaaabaabababbababbbbbaaab 1000000 acacac 1000000 acabac 1000000 acacabacacabacacac 1000000 aaaa 1