[Solution] Add Modulo 10 Codeforces Solution

E. Add Modulo 10

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given an array of n$n$ integers a1,a2,…,an$a_1,a_2,\dots ,a_n$

You can apply the following operation an arbitrary number of times:

• select an index i$i$ (1≤i≤n$1\le i\le n$) and replace the value of the element ai$a_i$ with the value ai+(aimod10)$a_i+(a_{i}mod10)$, where aimod10$a_{i}mod10$ is the remainder of the integer dividing ai$a_i$ by 10$10$.

For a single index (value i$i$), this operation can be applied multiple times. If the operation is applied repeatedly to the same index, then the current value of ai$a_i$ is taken into account each time. For example, if ai=47$a_i=47$ then after the first operation we get ai=47+7=54$a_i=47+7=54$, and after the second operation we get ai=54+4=58$a_i=54+4=58$.

Check if it is possible to make 

Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

 occupied

all array elements equal by applying multiple (possibly zero) operations.

For example, you have an array [6,11]$[6,11]$.

• Let's apply this operation to the first element of the array. Let's replace a1=6$a_1=6$ with a1+(a1mod10)=6+(6mod10)=6+6=12$a_1+(a_{1}mod10)=6+(6mod10)=6+6=12$. We get the array [12,11]$[12,11]$.
• Then apply this operation to the second element of the array. Let's replace a2=11$a_2=11$ with a2+(a2mod10)=11+(11mod10)=11+1=12$a_2+(a_{2}mod10)=11+(11mod10)=11+1=12$. We get the array [12,12]$[12,12]$.

Thus, by applying 2$2$ operations, you can make all elements of an array equal.

Input

The first line contains one integer t$t$ (1≤t≤104$1\le t\le {10}^4$) — the number of test cases. What follows is a description of each test case.

The first line of each test case contains one integer n$n$ (1≤n≤2⋅105$1\le n\le 2\cdot {10}^5$) — the size of the array.

The second line of each test case contains n$n$ integers ai$a_i$ (0≤ai≤109$0\le a_i\le {10}^9$) — array elements.

It is guaranteed that the sum of n$n$ over all test cases does not exceed 2⋅105$2\cdot {10}^5$.

Output

For each test case print:

• YES if it is possible to make all array elements equal;
• NO otherwise.

You can print YES and NO in any case (for example, the strings yEs, yes, Yes and YES will be recognized as a positive answer) .