FANCY - FANCY NUMBERS


Girls usually give only missed calls to their boyfriends and they want them to call back. These boys are now busy with their engineering subjects and cannot remember all girl friends’ mobile number. Because of this, girls make it easy for them by having fancy mobile numbers. A fancy mobile number may contain many continuous digits in it.

For example 9994442200 is a fancy mobile number because the boy can remember simply as triple nine, triple four, double two and double zero. As they are engineering students they do think different. One of the engineering students can spell the above number as double nine, nine, four, double four, two, two, double zero.

The number 100 has only 2 possibilities as it can be spelt as either one, zero, zero (or) one, double zero.

Given a mobile number find the number of possibilities that the number can be remembered.

Input

The first line consists of an integer t denoting the number of test cases. Each test case consists of a mobile number of length <= 30 digits.

Output

For each test case output the number of possibilities the number can be remembered.

Constraints

1 <= t <= 100000

Example

Input:
3
100
12345
11112

Output:
2
1
8

WARNING: Huge data set! Make your I/O optimizations.


hide comments
satya_jha123: 2015-08-29 18:44:37

[deleting spoiler]

Last edit: 2015-09-16 23:26:15
SangKuan: 2015-08-19 08:06:37

scanf is enough.no need to use getchar

PRIBAN91: 2015-06-15 13:23:12

Very unfair for JAVA coders! Does the problem setter has something against Java I wonder!!!

utkarsha gaumat: 2015-03-28 19:19:38

ac in one go

Ognjen Arsenijevic: 2015-03-18 15:29:02

60th on SPOJ :D

Hasil Sharma: 2013-07-02 12:19:40

third test case:
1.) 1,1,1,1
2.) 11,11
3.) 111,1
4.) 1,111
5.) 1111
6.) 11,1,1
7.) 1,1,11
8.) 1,11,1

Last edit: 2013-07-02 12:20:25
Himanshu: 2013-06-21 12:44:58

plz explain the 3rd test case !!!

Mitch Schwartz: 2012-06-19 16:57:24

@Darko: I did a short test, and I believe the only issue is that in at least one input file, the last line is not terminated by '\n'. (So you must be able to handle EOF.)

Last edit: 2012-06-19 17:07:39
Mitch Schwartz: 2012-06-09 18:48:07

To clarify: getchar() is fast enough for AC, only issue is that formatting may need to be dealt with defensively.

Btw @Tjandra: You know there is server instability, right? Submitting the same code a few seconds apart from each other may receive significantly different times, depending on the problem. I think submitting all of C, C++ 4.3.2, C++ 4.0.0-8, and C99 doesn't give a reliable indication of which compiler optimises best, rather it just clogs the rank table with 4 instances of your name.. Not that it's so important, but if you wish to remove a solution from the rank tables, you can disqualify the submission. (Note that if you want it to be hidden in your own status page for you, you must hide then disqualify, because after you disqualify there is no option to hide.)

Last edit: 2012-06-09 19:16:51
(Tjandra Satria Gunawan)(曾毅昆): 2012-06-09 15:40:27

@:D: yes, i agree with you, TLE with getchar and AC with scanf or gets ;)


Added by:cegprakash
Date:2011-12-26
Time limit:0.802s-1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64