package yukicoder; import java.io.PrintWriter; import java.util.Scanner; public class Q435 { static final int[] inv = new int[] { 0, 1, 5, 0, 7, 2, 0, 4, 8 }; public static void main(String[] args) { Scanner sc = new Scanner(System.in); PrintWriter pw = new PrintWriter(System.out); int T = sc.nextInt(); while (T-- > 0) { int n = Integer.parseInt(sc.next()); int x = Integer.parseInt(sc.next()); int a = Integer.parseInt(sc.next()); int b = Integer.parseInt(sc.next()); int m = Integer.parseInt(sc.next()); int reducedCombi = 1; int count3 = 0; int ans = 0; boolean f = true; int cur = x; for (int i = 0; i < n; ++i) { int combi = reducedCombi; if (i > 0) { cur = next(n, cur, a, b, m); reducedCombi = reducedCombi * inv[reduce3(i) % 9] * reduce3(n - 1 - i + 1) % 9; count3 = count3 - count3(i) + count3(n - 1 - i + 1); if (count3 >= 2) { combi = 0; } else if (count3 == 1) { combi = 3 * reducedCombi % 9; } else if (count3 == 0) { combi = reducedCombi % 9; } else if (count3 < 0) { throw new AssertionError(); } } ans = (ans + combi * (cur % 10)) % 9; if (f) if (cur % 10 > 0) f = false; } if (f) pw.println(0); else if (!f && ans == 0) pw.println(9); else pw.println(ans); } pw.close(); } static int count3(int n) { int c = 0; while (n > 0 && n % 3 == 0) { n /= 3; ++c; } return c; } static int reduce3(int n) { while (n > 0 && n % 3 == 0) n /= 3; return n; } static int next(int n, int cur, int a, int b, int m) { return ((cur ^ a) + b) % m; } }