NAC-SAC Game! (Easy)

Akash and Guru are playing an interesting game. They are standing at the two ends of the NAC-SAC bridge. Akash is currently standing at the NAC side of the bridge. And Guru is standing at the SAC side of the bridge. They both have a piece of paper in their hand in which initially number 1 is written down.

Wherever a person crosses from SAC to NAC, Akash multiplies his current number by 2 and writes it in the paper erasing the previous one. On the other hand, whenever a person crosses from NAC to SAC, Guru multiplies his current number by 3 and writes it in the paper erasing the number which was written previously.

When they are bored playing this game, they meet at the Plaza area where they show each other the numbers they finally got. They add up the numbers they got. As NSU is being crowded day by day, the numbers that Akash and Guru have got can be huge. So they are interested in calculating the remainder when the added up number is divided by 100003.

Input

The first line contains a positive integer T (1 ≤ T ≤ 100), which is the number of test cases. Then T cases follow, each having two lines. In the first line, there is a positive integer N (1 ≤ N ≤ 10000) which is the number of times Akash and Guru have seen people cross the bridge. Then a binary string S of length N follows (|S| = N). ‘0’ in the string indicates a person has crossed from SAC to NAC and ‘1’ in the string indicates a person has crossed from NAC to SAC.

Output

For each test case, output a single integer which is the remainder when the added value got by Akash and Guru is divided by 100003

Sample

Input	Output
3 2 00 4 1001 38 00110010111111111101001111011011110111	5 13 25974
In the first case, Akash has got 4 and Guru has got 1. After adding them up, they get 5. After dividing it by 100003 they finally get 5.