Problem hidden
This problem was hidden by Editorial Board member probably because it has incorrect language version or invalid test data, or description of the problem is not clear.
Problem hidden on 2014-09-23 02:24:54 by Piotr KÄ…kol

SECCODE - Secret code

John knows that secret code which he wants is a nonnegative integer of length n. The problem is that he knows only some of its digits. Now he doesn't know whether he should waste time trying all possible codes or will it last too long and he should get to know the code a bit better.

Input

The first line of the standard input contains one integer t (t<1001) which is number of test cases. Each test consists of one line with number n (n<101) - code's length and code x separated with a space. The code contains only digits and question marks if John doesn't know what digit to put on these positions.

Output

For each test print the number of possible secret codes.

Example

Input:
2
3 12?
5 1?2?3

Output: 10
100


Added by:Piotr Kąkol
Date:2013-09-15
Time limit:5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: SCM qobi
Resource:AlgoLiga 10
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.