열한 번째 생일

보랴의 열한 번째 생일이다. 보랴는 멋진 선물을 받았다. 숫자가 적힌 카드 $n$장이고, $i$번째 카드에는 $a_i$가 적혀 있다. 보랴는 카드를 한 줄로 늘어놓아 더 큰 수 하나를 만들려고 한다. 예를 들어 숫자 1, 31, 12가 적힌 카드를 이 순서대로 늘어놓으면 13112를 얻는다.

보랴는 아직 열한 살이지만, 카드를 늘어놓는 방법이 $n!$가지라는 것을 안다. 그런데 오늘은 특별한 날이라, 보랴는 만들어진 큰 수가 11로 나누어떨어지는 방법에만 관심이 있다. 그래서 앞 문단의 방법은 13112 = 1192 × 11이므로 좋은 방법이다. 하지만 카드를 31, 1, 12 순서로 늘어놓으면 31112가 되고, 이 수는 11로 나누어떨어지지 않으므로 좋은 방법이 아니다. 보랴가 좋은 방법의 수를 구할 수 있게 도와주자.

보랴는 같은 수가 적힌 카드라도 모두 다른 카드로 본다. 예를 들어 1이 적힌 카드가 두 장이면 좋은 방법도 두 가지다.

좋은 방법의 수를 구하자. 이 수는 클 수 있으므로 998244353으로 나눈 나머지를 출력한다.

입력 데이터는 여러 테스트 케이스로 이루어진다. 입력 데이터의 첫 줄에는 테스트 케이스의 수 $t$가 주어진다 ($1 \le t \le 100$). 테스트 케이스의 설명이 이어진다.

각 테스트 케이스는 두 줄로 이루어진다.

첫 줄에는 보랴가 선물로 받은 카드의 수 $n$이 주어진다 ($1 \le n \le 2000$).

둘째 줄에는 카드에 적힌 수 $n$개 $a_i$가 주어진다 ($1 \le a_i \le 10^9$).

한 입력 데이터의 모든 테스트 케이스에 있는 카드 수의 합은 2000을 넘지 않는다.

각 테스트 케이스마다 만들어진 큰 수가 11로 나누어떨어지도록 카드를 탁자에 늘어놓는 방법의 수를 998244353으로 나눈 나머지를 한 줄에 출력한다.