QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#102495	#5440. P-P-Palindrome	retcarizy^#	AC ✓	51ms	43652kb	C++14	1014b	2023-05-03 13:56:27	2023-05-03 13:56:29

Judging History

你现在查看的是最新测评结果

[2023-08-10 23:21:45]
System Update: QOJ starts to keep a history of the judgings of all the submissions.

[2023-05-03 13:56:29]
评测

测评结果：AC
用时：51ms
内存：43652kb

查看

[2023-05-03 13:56:27]
提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N=2e6+10;
char ch[N];
int n;
struct Palindromic_Automation{
	int cnt,trans[N][26],fail[N],last,len[N],num[N],n;
	void init(){
		cnt=2;
		fail[0]=fail[1]=1;
		len[1]=-1;
	}
	void init1(){
		last=0;
	}
	void extand(int c,int n){
		int u=last;
		while (ch[n]!=ch[n-len[u]-1])
			u=fail[u];
		if (!trans[u][c]){
			int v=cnt++;
			len[v]=len[u]+2;
			int w=fail[u];
			while (ch[n]!=ch[n-len[w]-1])
				w=fail[w];
			fail[v]=trans[w][c];
			trans[u][c]=v;
		}
		last=trans[u][c];
		num[last]++;
	}
	void solve(){
		long long sum=0;
		for (int i=2;i<cnt;i++){
			int x=len[i]-len[fail[i]];
			if (len[i]%x==0){
				int y=len[i]/x;
				sum+=1ll*y*y-1ll*(y-1)*(y-1);
			}else sum++;
		}
		printf("%lld\n",sum);
	} 
}pam;
int main(){
	pam.init();
	scanf("%d",&n);
	for (int i=1;i<=n;i++){
		scanf("%s",ch+1);
		int m=strlen(ch+1);
		pam.init1();
		for (int j=1;j<=m;j++) pam.extand(ch[j]-'a',j);
	}
	pam.solve();
}

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 1ms

memory: 3824kb

input:

2
aaaa
aaa

output:

result:

ok 1 number(s): "16"

Test #2:

score: 0

Accepted

time: 2ms

memory: 3832kb

input:

3
abaaa
abbbba
bbbaba

output:

result:

ok 1 number(s): "28"

Test #3:

score: 0

Accepted

time: 2ms

memory: 3696kb

input:

1
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab

output:

result:

ok 1 number(s): "15130"

Test #4:

score: 0

Accepted

time: 2ms

memory: 3828kb

input:

3
aaaaaaaaaaaaaaaaaaaaaaaaa
bbbbbbbbbbbbbbbbbbbbbbbbb
bababababababaabababababa

output:

result:

ok 1 number(s): "1282"

Test #5:

score: 0

Accepted

time: 7ms

memory: 10544kb

input:

5
ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff...

output:

3600000000

result:

ok 1 number(s): "3600000000"

Test #6:

score: 0

Accepted

time: 1ms

memory: 10648kb

input:

5
wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww...

output:

3600000000

result:

ok 1 number(s): "3600000000"

Test #7:

score: 0

Accepted

time: 4ms

memory: 18836kb

input:

3
abbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbab...

output:

result:

ok 1 number(s): "133586"

Test #8:

score: 0

Accepted

time: 11ms

memory: 17172kb

input:

3
abbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbabab...

output:

result:

ok 1 number(s): "118967"

Test #9:

score: 0

Accepted

time: 7ms

memory: 16656kb

input:

3
bbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabb...

output:

result:

ok 1 number(s): "114444"

Test #10:

score: 0

Accepted

time: 7ms

memory: 16800kb

input:

3
abbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbabab...

output:

result:

ok 1 number(s): "115321"

Test #11:

score: 0

Accepted

time: 2ms

memory: 18664kb

input:

3
azzazzazazzazzazazzazazzazzazazzazazzazzazazzazzazazzazazzazzazazzazazzazzazazzazzazazzazazzazzazazzazzazazzazazzazzazazzazazzazzazazzazzazazzazazzazzazazzazzazazzazazzazzazazzazazzazzazazzazzazazzazazzazzazazzazazzazzazazzazzazazzazazzazzazazzazzazazzazazzazzazazzazazzazzazazzazzazazzazazzazzazaz...

output:

result:

ok 1 number(s): "131825"

Test #12:

score: 0

Accepted

time: 4ms

memory: 3732kb

input:

3
yazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbyb...

output:

result:

ok 1 number(s): "6"

Test #13:

score: 0

Accepted

time: 8ms

memory: 3700kb

input:

3
azbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazby...

output:

result:

ok 1 number(s): "6"

Test #14:

score: 0

Accepted

time: 6ms

memory: 3884kb

input:

3
byazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyaz...

output:

result:

ok 1 number(s): "6"

Test #15:

score: 0

Accepted

time: 8ms

memory: 16144kb

input:

1
abbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbabaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaababbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbabaababbaabbabaababbabaabbaababbaabbabaabba...

output:

result:

ok 1 number(s): "113382"

Test #16:

score: 0

Accepted

time: 11ms

memory: 11740kb

input:

5
rrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrr...

output:

123447499

result:

ok 1 number(s): "123447499"

Test #17:

score: 0

Accepted

time: 0ms

memory: 8656kb

input:

5
tttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttt...

output:

25319820

result:

ok 1 number(s): "25319820"

Test #18:

score: 0

Accepted

time: 7ms

memory: 5456kb

input:

5
ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff...

output:

result:

ok 1 number(s): "2746507"

Test #19:

score: 0

Accepted

time: 14ms

memory: 20180kb

input:

3
oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo...

output:

1912677071

result:

ok 1 number(s): "1912677071"

Test #20:

score: 0

Accepted

time: 4ms

memory: 12172kb

input:

3
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxcxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...

output:

111259628

result:

ok 1 number(s): "111259628"

Test #21:

score: 0

Accepted

time: 10ms

memory: 7188kb

input:

3
cccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc...

output:

13754174

result:

ok 1 number(s): "13754174"

Test #22:

score: 0

Accepted

time: 8ms

memory: 5616kb

input:

3
dddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddd...

output:

result:

ok 1 number(s): "1867151"

Test #23:

score: 0

Accepted

time: 2ms

memory: 6060kb

input:

1
jjqjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjvjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjj...

output:

result:

ok 1 number(s): "1856484"

Test #24:

score: 0

Accepted

time: 10ms

memory: 5260kb

input:

1
vvvvvvvvvvvvvvvvvvvvvvvvvvvqvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvmvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvsvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvnvvvvvvvvvvvvvvvvvvvv...

output:

result:

ok 1 number(s): "190722"

Test #25:

score: 0

Accepted

time: 3ms

memory: 4756kb

input:

1
txxxxxxxxxxxxxxxxxxxxxxxxxxxxhxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxrxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxhxxxxxtxlxxxxxxxxxktxxxxxxxxxxxxxxxxxexxxxxxxxxxxxxxgxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxjxxxxxxxxxxxxxxxxxxxvxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxzqxxjxxxxxxxxxxxxxxx...

output:

result:

ok 1 number(s): "76004"

Test #26:

score: 0

Accepted

time: 5ms

memory: 11648kb

input:

1
gggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggg...

output:

81149988

result:

ok 1 number(s): "81149988"

Test #27:

score: 0

Accepted

time: 11ms

memory: 18160kb

input:

1
llllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllll...

output:

1272080790

result:

ok 1 number(s): "1272080790"

Test #28:

score: 0

Accepted

time: 13ms

memory: 27068kb

input:

1
eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee...

output:

12890286923

result:

ok 1 number(s): "12890286923"

Test #29:

score: 0

Accepted

time: 8ms

memory: 10460kb

input:

5
dgasxxawfuzttbnrniddspiplejfqzzoadnogyemjktjqqjtkjmeygondaozzqfjelpipsddinrnbttzufwaxxsagdvkrreghjrkkrjhgerrkvdgasxxawfuzttbnrniddspiplejfqzzoadnogyemjktjqqjtkjmeygondaozzqfjelpipsddinrnbttzufwaxxsagdvkrreghjrkkrjhgerrkvdgasxxawfuzttbnrniddspiplejfqzzoadnogyemjktjqqjtkjmeygondaozzqfjelpipsddinrnbt...

output:

result:

ok 1 number(s): "652993"

Test #30:

score: 0

Accepted

time: 9ms

memory: 10548kb

input:

5
jlpzojmatlmawicowbaazzfyzqdjodsyngoqfnxbshbjywkgafhdarnchbwcskosqxpdjffjdpxqsokscwbhcnradhfagkwyjbhsbxnfqognysdojdqzyfzzaabwociwamltamjozpljjlpzojmatlmawicowbaazzfyzqdjodsyngoqfnxbshbjywkgafhdarnchbwcskosqxpdjffjdpxqsokscwbhcnradhfagkwyjbhsbxnfqognysdojdqzyfzzaabwociwamltamjozpljjlpzojmatlmawicowb...

output:

result:

ok 1 number(s): "425510"

Test #31:

score: 0

Accepted

time: 2ms

memory: 10464kb

input:

5
zwzxfvwcwglyetqbpgxubiqntaydeqmdpassapdmqedyatnqibuxgpbqteylgwcwvfxzwzjeiveeviejzwzxfvwcwglyetqbpgxubiqntaydeqmdpassapdmqedyatnqibuxgpbqteylgwcwvfxzwzjeiveeviejzwzxfvwcwglyetqbpgxubiqntaydeqmdpassapdmqedyatnqibuxgpbqteylgwcwvfxzwzjeiveeviejzwzxfvwcwglyetqbpgxubiqntaydeqmdpassapdmqedyatnqibuxgpbqte...

output:

result:

ok 1 number(s): "1180524"

Test #32:

score: 0

Accepted

time: 4ms

memory: 10464kb

input:

5
rmgwqmkvznpmdkqiiqkdmpnzvkmqwgmrpocxxcoprmgwqmkvznpmdkqiiqkdmpnzvkmqwgmrpocxxcoprmgwqmkvznpmdkqiiqkdmpnzvkmqwgmrpocxxcoprmgwqmkvznpmdkqiiqkdmpnzvkmqwgmrpocxxcoprmgwqmkvznpmdkqiiqkdmpnzvkmqwgmrpocxxcoprmgwqmkvznpmdkqiiqkdmpnzvkmqwgmrpocxxcoprmgwqmkvznpmdkqiiqkdmpnzvkmqwgmrpocxxcoprmgwqmkvznpmdkqiiq...

output:

result:

ok 1 number(s): "4551019"

Test #33:

score: 0

Accepted

time: 7ms

memory: 10688kb

input:

5
tnzbhxooxhbzntlskksltnzbhxooxhbzntlskksltnzbhxooxhbzntlskksltnzbhxooxhbzntlskksltnzbhxooxhbzntlskksltnzbhxooxhbzntlskksltnzbhxooxhbzntlskksltnzbhxooxhbzntlskksltnzbhxooxhbzntlskksltnzbhxooxhbzntlskksltnzbhxooxhbzntlskksltnzbhxooxhbzntlskksltnzbhxooxhbzntlskksltnzbhxooxhbzntlskksltnzbhxooxhbzntlskk...

output:

18042012

result:

ok 1 number(s): "18042012"

Test #34:

score: 0

Accepted

time: 7ms

memory: 10460kb

input:

5
wosalwxbdgvouchgnkqygjphbtpoxduzlpmpbuhhmwvgsbrfolbykyjzoukregdyxskkinjqzjeuublzpuukcaazbsggluyqlmyiallofjebbukuqcalufrqdjjkgvooretzaasgnpnztfalutzztulaftznpngsaazteroovgkjjdqrfulacqukubbejfollaiymlqyulggsbzaackuupzlbuuejzqjnikksxydgerkuozjykyblofrbsgvwmhhubpmplzudxoptbhpjgyqknghcuovgdbxwlasowovxg...

output:

result:

ok 1 number(s): "61625"

Test #35:

score: 0

Accepted

time: 2ms

memory: 10224kb

input:

5
pyybsfiukgpneuwnykmxylcpaujvzpvcubdlvljkdwxkniwznzqvfblfedmydoqqrysksoobrwsqguocoxtfnisqmtbbieekshiwrzrbluflrtzfxwkvqtplcinkqqjsxogdsyucodbzhhnzaluymttfnzovqnevrqtbtqpmtgsfvnenstchzhdrequfxuasnkoxexafwpbgzqaobiicvmwugeugfgpmjvfphfojacdfhjplypqfoxzoacnfoucbhlqqnxxywfdaykxbsfkkkbwuryfwowvhecdgtnzcnp...

output:

result:

ok 1 number(s): "57998"

Test #36:

score: 0

Accepted

time: 8ms

memory: 8944kb

input:

5
pndpupqzhnvxfilkpqdiabywphmclxjchfoctreacxnxwernjkhtyrgokfjpcuuqstsoserfmhfnrgdhzsioknvrhqflrjfkgkjrtoouchgeduceggstnsraurhpxgreryesioloxkcnndjdzyrfmksunizovolqltamzkmaggqftuvwjnkrhgyewthkqchdrgqrkwdfdwdoqunjulkpykaavlinxbzfuzzoqyvwrsfgmtvrzoyidesgkfwtbunicodseljtsxdzxpvpjnbaunefavrjjzhufqqsvekbpl...

output:

result:

ok 1 number(s): "46840"

Test #37:

score: 0

Accepted

time: 8ms

memory: 37972kb

input:

1
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

90000000000

result:

ok 1 number(s): "90000000000"

Test #38:

score: 0

Accepted

time: 7ms

memory: 4016kb

input:

5
nmnnmnnmnnmnnmmmnnmmmmmnnnnnmmnmnnnnnmmnmmmnnnmnmnmnmmmmmnnnnmnnnmnnnmmmnmnmmmmnmmnmmmnnnnmmmmmnmnnmmmnmmnmmnmmmnnnmmmnmmnnnmmmnnmnnnmnmmmnnnnmmmnmnnmnmmmmnnnnnnnmnnnmmmmnmmnnnmnnnmmmnnmmnmnmmnnmmmmnnmnnnmmmmmmnmmnnnmnnnnnmmnmnmmnmnnnmnmmnmnmmmnnmmnmnnnmnmmmmnmnnnmmmnmnmmnnnnnmmmnnmnnnnnnmmmmmmmnm...

output:

result:

ok 1 number(s): "4526"

Test #39:

score: 0

Accepted

time: 3ms

memory: 4128kb

input:

5
aaupapuupauuauapupapauauuuuuaapauuaaapppuauuppupuapappuapuuuuaupappaauupapppuppauuaauppuappaappaupaaapaapupuuapaauuuppppuaapaaauuapupuaaapppuuaaapuuuapuaupaaapupaauaapuaapaaaaupuuuupupuapaaaapaupaaaapppuapapuauauapuaauuapapuappauauappuappppuppaauapapuapuauuapupaupaauauupaauapuaupauauuapaappaapaapp...

output:

result:

ok 1 number(s): "2372"

Test #40:

score: 0

Accepted

time: 8ms

memory: 3884kb

input:

5
bkdbddddvddkvkvdbkvdvbbdkkkvvkbvbvbvvbvvvkdbdkkkdvbdkdkvbbbbkbbvbkddkbdvbkkkbdvvdkkdvkbkkdvddbdvdkkdkvbkkdkkbvddddvdvvkkvbbdvkkvkbkkkkkvddbbkdkbvdkbkkdvkvvvvkbkkvkbbdvbkdbkdbkvkkkkvkvkkvvkkvkbbvbvbbbvkbvbvkkvkvkbvbdvvdkkvdbkvbdvvdkvddvvddvkdbkbbvkbvdbvvdddkbdddvbbbdvvdddvdkbdkbkkdbvbkdvdddvddbkkvk...

output:

result:

ok 1 number(s): "2339"

Test #41:

score: 0

Accepted

time: 2ms

memory: 3836kb

input:

2
afffafafaa
afaafaafaf

output:

result:

ok 1 number(s): "29"

Test #42:

score: 0

Accepted

time: 7ms

memory: 4084kb

input:

5
wjdulwwjulujdddljudwwlddduddujljjjdluljwddjuddddljwjuujdllllljuudddjwududddudllwudluldwudddwdllldlwwwdjlwuwwlddlluluwdlldjuudujdjujddwduwwjwlluudjjujjdudlljwdwduwjdljlwdjddwddddludwuuwlddddddljddlduddwldwddllduwjwddjdulwddjwddddwujwluujjjludwjddwwdjwddulldjwljudjljljduddjlddjujdddddudduljduuuljwul...

output:

result:

ok 1 number(s): "2063"

Test #43:

score: 0

Accepted

time: 51ms

memory: 3828kb

input:

1000000
i
n
l
f
q
i
s
m
u
x
r
v
v
u
b
m
o
u
s
q
k
t
t
c
n
t
y
m
x
q
k
v
h
q
s
w
o
b
o
y
n
s
f
w
d
d
y
d
l
i
e
r
c
l
e
d
h
h
c
l
x
q
f
l
v
j
q
j
p
o
e
s
l
w
u
h
q
f
j
g
l
h
v
x
k
w
t
h
o
b
e
s
x
c
m
v
r
r
p
w
d
g
r
u
g
d
j
a
a
c
w
t
u
h
x
i
l
s
o
z
i
m
p
h
j
u
p
t
g
f
p
w
x
f
o
w
u
m
a
k
p
p
q
x
n
r
...

output:

result:

ok 1 number(s): "26"

Test #44:

score: 0

Accepted

time: 40ms

memory: 3656kb

input:

1000000
u
i
n
f
z
i
g
y
o
t
a
t
y
q
m
g
u
z
t
j
j
s
f
r
f
z
a
e
k
s
q
u
p
e
o
l
x
g
q
b
l
w
x
c
u
x
j
e
s
e
y
r
r
v
v
i
d
p
q
e
q
q
z
a
d
i
e
y
w
p
e
x
m
n
e
f
j
l
c
y
x
i
d
a
m
k
w
q
y
j
c
u
y
h
k
l
y
j
r
e
r
b
n
i
w
r
o
i
q
m
o
r
x
d
s
u
n
i
w
r
t
g
c
i
d
h
n
a
x
h
t
c
s
h
c
j
c
i
b
z
u
z
c
b
e
k
...

output:

result:

ok 1 number(s): "26"

Test #45:

score: 0

Accepted

time: 39ms

memory: 3792kb

input:

1000000
c
c
b
c
b
b
a
c
c
b
c
b
a
a
a
a
c
b
a
c
c
c
c
b
c
a
c
c
b
a
a
a
c
c
b
b
c
a
c
a
c
c
c
c
a
b
c
b
a
b
c
a
a
a
b
c
a
c
b
c
b
a
c
b
a
b
c
c
a
c
b
c
a
b
c
c
b
a
a
a
c
b
c
a
b
b
c
b
a
a
c
c
c
b
b
a
b
a
c
b
a
b
c
b
b
b
a
b
a
a
c
a
b
b
c
a
a
c
c
b
a
a
c
b
a
b
a
b
b
b
b
b
c
a
b
b
c
a
a
a
b
a
b
b
a
c
...

output:

result:

ok 1 number(s): "3"

Test #46:

score: 0

Accepted

time: 10ms

memory: 4972kb

input:

1
alngdzgfsplrmhhyblurpjxyqhrxmbyyubvvxtmuwrnfimiggwhsoluetintakqfohgtmtampxljpkawolbuyrsrmdjapecfytjcfxcdcyymbfaqshkujxxypteohceukrejaveenkmsdxrmpdlapcnsnowykiiqisgdratbqcwxfzspkglkqghmcsiqwemkilaisqucgithhcrjvoydpnmtmxdwsmjfjtimsqpvesagpqucssfwyricarvcpcujfsxupluoxxkzelyjqewsptiyobhrvdatjhbcohcdfd...

output:

result:

ok 1 number(s): "3195"

Test #47:

score: 0

Accepted

time: 4ms

memory: 4856kb

input:

1
ghbhcdfhccifjigghcfhejhfcaibghfhehehjichadijbiihajddhgjgbdibecjjcaagedfaafejcfjjgdaiebcjihecjicadacefgbajeafccjdbafdjhjddjggbdhgdijbbiadeabbaiieacbeighagbaajgdbdajgajcabhcgfcadbadigjhehaibighhdjhaeggefhgfcfhaahhchedcjhbaedihgfgjiejeifbdieacghbghfjdjfehfgdfadeeghdjdcghibjdhiiggdchdbihfchbhchaeefccb...

output:

result:

ok 1 number(s): "3395"

Test #48:

score: 0

Accepted

time: 16ms

memory: 5084kb

input:

1
fgffhhghheehgggfgghdeeeedgfdhdfehghhegeeggfhgdfhgfgedgdgdegedhegeedddefdfedhfgdhghehhggehdffdfgddhegeghefffgddedfeeggfheghhgghhhehfefhfegfgghfffdhfddgheegdgefdhhegfffefghhehgggheegdggddeggdehddhdfefgeffdgfdghefgegdhegdfggeggddhhddefghfgedhhdeghgfedhddefdhfhfdhfdghhegedfhdeefffegedddgfgefheffeeeedd...

output:

result:

ok 1 number(s): "4178"

Test #49:

score: 0

Accepted

time: 19ms

memory: 6820kb

input:

100
xuxmuutatmmtxmautmmttuuaatmtamxmutxautxxttmuamtxaaumaautaaattmmmxumtxaaxmxxmmumuttmututmtmuauutuuuumtuaxmaaxattxattuuxumxtummmttmmutmmataxuuttattmatumxxatuxumatxutmtuuaaatxatutmmtutauauuuuxumataxtamauttaaxxuttaaxtauamammxumauxumuuutmuxmauxutuxuxtutmtatuxttxtummtxutxmaxuuxxtxuatuamuxaatuatuauxxmu...

output:

result:

ok 1 number(s): "30276"

Test #50:

score: 0

Accepted

time: 24ms

memory: 6612kb

input:

100
wddldawddddlwwawawdwdldldldldawdwwdwaaddlddddadwladdddaddawadladlwldlalldddlddlddwdlwwddaddllwwdldddwwldddaadwadddddlddlwwdawawdwaawadadadldddwaaldadallwdwlwdlddadlddladdlddddaaddddlwwdaalddddwldaddadaddwawwalaalladdalllddadwddddadlwlddlddwldaadlwddwlldddadwwaddaaldddwwlddddddwddadddalwawddwdawd...

output:

result:

ok 1 number(s): "30213"

Test #51:

score: 0

Accepted

time: 20ms

memory: 5360kb

input:

100
ygripyrkwoyooyykfppktyktktikoyyogttiorfyptgtogkygrtkiwgyoipkpkkiiikypgftggfpktrwoygfwptwpwfyptpwrwyigyokwprkfpkfkfwpfykrfygoyykkgfigyktyryrfpkfwoipoipotypiifpyooykkpokgopooykywyiwgoypwtwygfikorpoirptfffkwirriyyyypfpkiwrpyfgtwrtfyfotpttfrwpfoprftpyigfrtggpwifypwyfpowpripgtfrgkyirkrorfgrorwpopioig...

output:

result:

ok 1 number(s): "16720"

Test #52:

score: 0

Accepted

time: 26ms

memory: 42884kb

input:

100
ywwcynkynntwwqtcyjcnkjtkwctnqwcttnnqwqjjqjjwykwwyjwnywkwqwnjytqkyyjwqwwycyycjtqyqyjyqqynqwwtnwcjwjckjnnywjwwjntnwwjywywwwkwwtcqnkqqjqqwkknnykjcynwnyyqwjwyjckkcnqyqwkywyykkwcwwwkcknkwttnqyqytnttyjqtwwywqyytywkcwyqnqwywwwtwywjwqjwcwcqwkqcqnywkkwyncjwtkcwqtjycywtjkywyknyjqcwqwtywqjktwytkcwykwknnwyj...

output:

result:

ok 1 number(s): "346933"

Test #53:

score: 0

Accepted

time: 7ms

memory: 43652kb

input:

100
nmxxmmvdyyfnmmvmmunvmfmvrnddnryrmdrvuurmuvnmudnnrrmyvmvuvdxvyxvmumnnrxummffuvdrmxnydfxnxfnxmnvmyfnmuyxruxfymyryunrmfmdmmxmufnmmmmmryrnfmrrvrfvfdxumymxmmxmxxmnfyddmmurvfvumfmxrmvfmnxnmnrvmyxfyrvnyfyyvvrmryynruyxmfmvmxxmrxrvmxudyvfxndrnvunvmnyxvyfvvxrndmffdvrfvfmmufdumxdvmumvmmxnmxdudyyfrdvmrxvyyx...

output:

result:

ok 1 number(s): "354764"

Test #54:

score: 0

Accepted

time: 18ms

memory: 30652kb

input:

100
hohohoohoohhoohhhhhhohohhhooohhohoooohohhhoooohohhhoohhooohhhooohhoooohooooooohohhhoohohohhhohoohhohhohhoohohhhohohoohhhohooooooohoooohhooohhhooohhoohhhohoooohhhohoooohohhooohhhohohhhhhhoohhoohoohohohhohhoohohhhohohoohhhohooooooohoooohhooohhhooohhoohhhohoooohhhohoooohohhooohhhohohhhhhhoohhoohooh...

output:

400202791

result:

ok 1 number(s): "400202791"

Test #55:

score: 0

Accepted

time: 9ms

memory: 29128kb

input:

100
yyyyyjyyjjjyyjjjjjyjyyyjyyjyyjyyyjyyyyjjyyjjjyyyjyyyyjjjyyyjjyjyyyyyyyyyjjjyyjjyjjjyyyyjjjyyyyjyyyyyyyyyyjyyyyjjjyyyyjjjyjjyyjjjyyyyyyyyyjyjjyyyjjjyyyyjyyyjjjyyjjyyyyjyyyjyyjyyjyyyjyjjjjjyyjjjyyjyyyyyyyyyyjyyjjjyyjjjjjyjyyyjyyjyyjyyyjyyyyjjyyjjjyyyjyyyyjjjyyyjjyjyyyyyyyyyjjjyyjjyjjjyyyyjjjyyyyjy...

output:

200209587

result:

ok 1 number(s): "200209587"

Test #56:

score: 0

Accepted

time: 25ms

memory: 26628kb

input:

100
coppocpcpccpccppocopcooccopopccopccocccpocooccocpcppccocoppcocoppcoocoopopoooopppopppoccppccpcppccoccoccppcpccppccopppopppoooopopoocoocppococppococcppcpcoccoocopcccoccpoccpopoccoocpocoppccpccpcpcoppoccoccppcpccppccopppopppoooopopoocoocppococppococcppcpcoccoocopcccoccpoccpopoccoocpocoppccpccpcpco...

output:

result:

ok 1 number(s): "203651"