Given a natural number in the form of a linked list, add 1 to it.

Examples

Linked List: 7→8→9
Resultant List: 7→9→0

Linked List: 9→9→9
Resultant List: 1→0→0→0

Testing

Input Format

The first line contains an integer ‘T’ denoting the number of independent test cases.

For each test case the input has two lines:

• An integer ‘n’ denoting the length of the linked list.
• n space-separated integers denoting the digits of the number.

Output Format

For each test case, a line containing integers denoting the digits of the result.

Sample Input

3
3
7 8 9
3
9 9 9
1
0

Expected Output

7 9 0
1 0 0 0
1

Constraints

1 <= T <= 100

1 <= n <= 104

0 <= element <= 9