Submit | All submissions | Best solutions | Back to list |

Problem
hidden on 2014-09-23 02:24:54 by Piotr KÄ…kol
## SECCODE - Secret code |

Wersja polska | English version |

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?3Output: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 |