Time Limit:1000ms Memory Limit:65536KB |

## Description |

Mengqian has attracted overwhelming boys after March 11. Mengqian claims that she preferred the boy with persistence. In order to choose her boy, she delegated the ACM team of UESTC to publish her puzzle. The puzzle is called ¡°Persistence of Number¡±, which consists of 32 nonnegative integers, each 32-digit long. Then she asked suitors to calculate the persistence of the product of the 32 integers. The one who first solve this puzzle would win Mengqian¡¯s heart. The persistence of an integer denotes a digit generated by replace the integer by the sum of its digits until one reaches a single digit. For example, the persistence of 19890902 is 2, because 1 + 9 + 8 + 9 + 0 + 9 + 0 + 2 = 38, 3 + 8 = 11, 1 + 1 = 2. Wolverine is a crazy suitor of Mengqian with brilliant minds. He said he can solve this problem in ten minutes. Can you beat him? |

## InputThe first line of the input is an integer T (T <= 311), which stands for the number of test cases you need to solve. Each case consist of 32 lines, each line denotes a 32-digit long integer. |

## OutputFor each case, print a digit on a single line, which is the persistence of the product of the 32 integers. |

## Sample Input1 10000000000000000000000000000000 01000000000000000000000000000000 00100000000000000000000000000000 00010000000000000000000000000000 00001000000000000000000000000000 00000100000000000000000000000000 00000010000000000000000000000000 00000001000000000000000000000000 00000000100000000000000000000000 00000000010000000000000000000000 00000000001000000000000000000000 00000000000100000000000000000000 00000000000010000000000000000000 00000000000001000000000000000000 00000000000000100000000000000000 00000000000000010000000000000000 00000000000000001000000000000000 00000000000000000100000000000000 00000000000000000010000000000000 00000000000000000001000000000000 00000000000000000000100000000000 00000000000000000000010000000000 00000000000000000000001000000000 00000000000000000000000100000000 00000000000000000000000010000000 00000000000000000000000001000000 00000000000000000000000000100000 00000000000000000000000000010000 00000000000000000000000000001000 00000000000000000000000000000100 00000000000000000000000000000010 00000000000000000000000000000001 |

## Sample Output1 |

## Hint |

## Author |

## SourceThe 8th UESTC Programming Contest Final |