Time Limit: 1000 MS    Memory Limit: 131072 K 


Description

As we all know, Mr Frog is famous for his wisdom and extensive knowledge. He knows so many languages. One day, he invents a totally new language HA which only contains 0 and 1. He sets some grammatical rules for the language. Only these 01 strings are correct HA sentences. 1. A empty string is a correct HA sentence. 2. "01" is a correct HA sentence. 3. If s1 and s2 both are correct HA sentences, s1 + s2 is a correct HA sentences. 4. If S is a correct HA sentence, "0" + S + "1" is a correct HA sentence. One day Mr Frog is very angry because someone give him an essay in HA language which contains some grammatical mistakes. He want you to insert into the essay as few '0' or '1' as possible so that the essay is a correct HA sentence. He also want you tell him how many different correct HA sentences you can get.

Input

The first line contains a single integer T(1<=T<=10): the number of cases. For each case, there is a 01 sequence S indicating the essay(1 <= |S| <= 1000).

Output

For each case, output two integers in a single line, the minimum number of '0' or '1' need to be inserted into S and the number of correct HA sentences you can get.

Sample Input

1 011

Sample Output

1 2

Hint

You can get these correct HA sentences by inserting a '0': 0011, 0101