Eleventh Birthday

오늘은 보랴의 열한 번째 생일이며, 그는 숫자가 적힌 n장의 카드라는 멋진 선물을 받았다. i-th 카드에는 숫자 ai가 적혀 있다. 보랴는 더 큰 숫자 하나를 만들기 위해 카드를 한 줄로 놓으려고 한다. 예를 들어 보랴에게 숫자 1, 31, 12가 적힌 카드가 있고 이 순서로 한 줄에 놓으면, 숫자 13112를 얻게 된다.

보랴는 겨우 11살이지만, 카드를 한 줄로 놓는 방법이 n!가지라는 것을 이미 알고 있다. 하지만 오늘은 특별한 날이므로, 그는 만들어진 큰 수가 십일로 나누어떨어지는 방법에만 관심이 있다. 따라서 앞 문단의 방법은 좋은데, 13112 = 1192 × 11이기 때문이다. 하지만 카드를 31, 1, 12의 순서로 놓으면 숫자 31112를 얻게 되고, 이는 11로 나누어떨어지지 않으므로 보랴에게 좋은 방법이 아니다. Help Borya 카드를 놓는 좋은 방법이 몇 가지인지 알아낸다.

보랴는 일부 카드에 같은 숫자가 적혀 있더라도 모든 카드를 서로 다른 것으로 간주한다. 예를 들어 보랴에게 1이 적힌 카드가 두 장 있다면, 좋은 방법은 두 가지이다.

Help Borya, 카드를 놓는 좋은 방법의 수를 구한다. 이 수는 클 수 있으므로 998244353으로 나눈 나머지를 출력한다.

입력 데이터에는 여러 테스트 케이스가 포함된다. 입력 데이터의 첫 번째 줄에는 테스트 케이스의 수인 정수 t가 주어진다 (1 ≤ t ≤ 100). 이어서 테스트 케이스에 대한 설명이 주어진다.

각 테스트는 두 줄로 설명된다.

첫 번째 줄에는 보랴가 선물로 받은 카드의 수인 정수 n (1 ≤ n ≤ 2000)이 주어진다.

두 번째 줄에는 카드에 적힌 숫자인 n개의 정수 ai (1 ≤ ai ≤ 109)가 주어진다.

하나의 입력 데이터에 포함된 모든 테스트의 카드 수의 총합은 t 2000을 넘지 않음이 보장된다.

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