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.